\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm}{}\section{Introduction\+To\+Algorithm\+:\+:Graph\+Algorithm Namespace Reference}
\label{namespace_introduction_to_algorithm_1_1_graph_algorithm}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}


Namespace of \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm}{Graph\+Algorithm}.  


\subsection*{Classes}
\begin{DoxyCompactItemize}
\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_a_d_j_list_graph}{A\+D\+J\+List\+Graph}
\begin{DoxyCompactList}\small\item\em A\+D\+J\+List\+Graph：图的邻接表表示，算法导论22章22.1节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_b_f_s___vertex}{B\+F\+S\+\_\+\+Vertex}
\begin{DoxyCompactList}\small\item\em B\+F\+S\+\_\+\+Vertex：用于广度优先搜索的顶点类型，算法导论22章22.2节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_d_f_s___vertex}{D\+F\+S\+\_\+\+Vertex}
\begin{DoxyCompactList}\small\item\em D\+F\+S\+\_\+\+Vertex：用于深度优先搜索的顶点类型，算法导论22章22.3节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_edge}{Edge}
\begin{DoxyCompactList}\small\item\em Edge：图的边，算法导论22章22.1节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_flow_vertex}{Flow\+Vertex}
\begin{DoxyCompactList}\small\item\em Flow\+Vertex：推送-\/重贴标签算法图的顶点，算法导论26章26.4节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_front_flow_vertex}{Front\+Flow\+Vertex}
\begin{DoxyCompactList}\small\item\em Front\+Flow\+Vertex：relabel\+\_\+to\+\_\+front算法的图的结点的数据结构，算法导论26章26.4节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_graph}{Graph}
\begin{DoxyCompactList}\small\item\em Graph：图，算法导论22章22.1节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list}{List}
\begin{DoxyCompactList}\small\item\em List：链表数据结构 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list_node}{List\+Node}
\begin{DoxyCompactList}\small\item\em List\+Node：链表结点的数据结构 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_matrix_graph}{Matrix\+Graph}
\begin{DoxyCompactList}\small\item\em Matrix\+Graph：图的矩阵表示，算法导论22章22.1节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_set_vertex}{Set\+Vertex}
\begin{DoxyCompactList}\small\item\em Set\+Vertex：图的顶点，它带一个node属性，算法导论22章22.1节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_vertex}{Vertex}
\begin{DoxyCompactList}\small\item\em Vertex：图的顶点，算法导论22章22.1节 \end{DoxyCompactList}\item 
struct \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_vertex_p}{Vertex\+P}
\begin{DoxyCompactList}\small\item\em Vertex\+P：图的顶点，它带一个parent属性，算法导论22章22.1节 \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Functions}
\begin{DoxyCompactItemize}
\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::pair$<$ std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type,Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$, std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type,Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_ab951caca0797ff2907a180fe81609c70}{floyd\+\_\+warshall} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)
\begin{DoxyCompactList}\small\item\em floyd\+\_\+warshall：返回所有节点对的最短路径的floyd\+\_\+warshall算法。算法导论25章25.2节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::shared\+\_\+ptr$<$ \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_graph}{Graph}$<$ Graph\+Type\+::\+N\+U\+M+1, typename Graph\+Type\+::\+Vertex\+Type $>$ $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a267d39a5bb09200f37a1cd2f0ad4f69f}{graph\+\_\+plus\+\_\+1v} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)
\begin{DoxyCompactList}\small\item\em graph\+\_\+plus\+\_\+1v：根据图graph生成一个新图。算法导论25章25.2节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type,Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a856b132d068d0553355203a16cdec97d}{johnson} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)
\begin{DoxyCompactList}\small\item\em johnson：返回所有节点对的最短路径的johnson算法。算法导论25章25.3节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Matrix\+Type $>$ }\\Matrix\+Type \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a680307505286ae3230d1843c342e874e}{extend\+\_\+path} (const Matrix\+Type \&L, const Matrix\+Type \&W)
\begin{DoxyCompactList}\small\item\em extend\+\_\+path：扩展一条边，算法导论25章25.1节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type,Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_ab9dcca59a42c708c137571d194c45bd9}{matrix\+\_\+shortest\+\_\+path} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)
\begin{DoxyCompactList}\small\item\em matrix\+\_\+shortest\+\_\+path：返回所有节点对的最短路径的矩阵乘法算法。算法导论25章25.1节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type,Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a6eb979447eeb937df4158f9646e20dde}{matrix\+\_\+shortest\+\_\+path\+\_\+fast} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)
\begin{DoxyCompactList}\small\item\em matrix\+\_\+shortest\+\_\+path：返回所有节点对的最短路径的矩阵乘法复平方算法。算法导论25章25.1节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a31fe8fc6f732112632c51221e739a7d4}{connected\+\_\+component} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)
\begin{DoxyCompactList}\small\item\em connected\+\_\+component：无向图的连通分量，算法导论21章21.1节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\bool \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_ac368f242de9f06c7d936cba4aa0ab40b}{same\+\_\+component} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type id1, typename Graph\+Type\+::\+V\+I\+D\+Type id2)
\begin{DoxyCompactList}\small\item\em same\+\_\+component：返回无向图的两个顶点是否位于同一个连通分量中。算法导论21章21.1节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a8839165b9e3d4c8c2ccac4cdc28aadd5}{breadth\+\_\+first\+\_\+search} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type)$>$ pre\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type)\{\}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type)$>$ post\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type)\{\})
\begin{DoxyCompactList}\small\item\em breadth\+\_\+first\+\_\+search：广度优先搜索，算法导论22章22.2节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a5fbba98b1c6a8b55f026158acc815768}{visit} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type v\+\_\+id, int \&time, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ pre\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type, int)\{\}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ post\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type, int)\{\})
\begin{DoxyCompactList}\small\item\em visit：深度优先搜索的辅助函数，用于访问顶点，算法导论22章22.3节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a9f44099f26242f50087b3cc16dff965f}{depth\+\_\+first\+\_\+search} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ pre\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type, int)\{\}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ post\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type, int)\{\}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ pre\+\_\+root\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type, int)\{\}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ post\+\_\+root\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type, int)\{\}, const std\+::vector$<$ typename Graph\+Type\+::\+V\+I\+D\+Type $>$ \&search\+\_\+order=std\+::vector$<$ typename Graph\+Type\+::\+V\+I\+D\+Type $>$())
\begin{DoxyCompactList}\small\item\em depth\+\_\+first\+\_\+search：深度优先搜索，算法导论22章22.3节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\const std\+::vector$<$ std\+::vector$<$ typename Graph\+Type\+::\+V\+I\+D\+Type $>$ $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a6d058c2aaa8714778b3f2ab8a24ff232}{scc} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)
\begin{DoxyCompactList}\small\item\em scc：强连通分量，算法导论22章22.5节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::vector$<$ typename Graph\+Type\+::\+V\+I\+D\+Type $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a804241e72be5f4c031190bc12a6b73a2}{topology\+\_\+sort} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)
\begin{DoxyCompactList}\small\item\em topology\+\_\+sort：拓扑排序，算法导论22章22.4节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_acc8cd65d7cf2d584f86cfd92494bdbf4}{create\+\_\+\+Gf} (const std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)
\begin{DoxyCompactList}\small\item\em create\+\_\+\+Gf：根据指定流网络生成一个残余网络。算法导论26章26.2节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a23a29754883e1edd7bd95a76634444a2}{ford\+\_\+fulkerson} (const std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)
\begin{DoxyCompactList}\small\item\em ford\+\_\+fulkerson：最大流的ford\+\_\+fulkerson算法。算法导论26章26.2节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_abd520b7e33d8c1e72b05210d784ac258}{push} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type u\+\_\+id, typename Graph\+Type\+::\+V\+I\+D\+Type v\+\_\+id, std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)
\begin{DoxyCompactList}\small\item\em push：generic\+\_\+push\+\_\+relabel算法的push操作。算法导论26章26.4节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\Graph\+Type\+::\+V\+I\+D\+Type \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a27dfe859312abba6639bca7b232d4bd6}{min\+\_\+v\+\_\+at\+\_\+\+Ef} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type u\+\_\+id, const std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)
\begin{DoxyCompactList}\small\item\em min\+\_\+v\+\_\+at\+\_\+\+Ef：relabel操作中的min\+\_\+v\+\_\+at\+\_\+\+Ef操作。算法导论26章26.4节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a143924362cc9f23ca452c3ca0e292ff3}{relabel} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type u\+\_\+id, const std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)
\begin{DoxyCompactList}\small\item\em relabel：generic\+\_\+push\+\_\+relabel算法的relabel操作。算法导论26章26.4节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_aeaf3e258f5ae9aed76158255fa603c00}{initialize\+\_\+preflow} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)
\begin{DoxyCompactList}\small\item\em initialize\+\_\+preflow：generic\+\_\+push\+\_\+relabel算法的初始化操作。算法导论26章26.4节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_ab134ec014d01e25ec2ed7d2c97babe23}{generic\+\_\+push\+\_\+relabel} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)
\begin{DoxyCompactList}\small\item\em generic\+\_\+push\+\_\+relabel：最大流的推送-\/重贴标签算法。算法导论26章26.4节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a2ae42c12c93664d94b5a6f9980fe8540}{discharge} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type u\+\_\+id, std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)
\begin{DoxyCompactList}\small\item\em discharge：最大流的前置重贴标签算法中的释放操作。算法导论26章26.5节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\\hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list}{List}$<$ \hyperlink{struct_introduction_to_algorithm_1_1_graph_algorithm_1_1_list_node}{List\+Node}$<$ typename Graph\+Type\+::\+Vertex\+Type $>$ $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_ad6a1917551c87991625d8402593ec863}{create\+\_\+\+L} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)
\begin{DoxyCompactList}\small\item\em create\+\_\+\+L：前置重贴标签算法中的创建\+L链表操作 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_af1dfc9c1874850fb1415db3644497777}{initial\+\_\+vertex\+\_\+\+N\+List} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)
\begin{DoxyCompactList}\small\item\em initial\+\_\+vertex\+\_\+\+N\+List：前置重贴标签算法中的初始化邻接链表操作 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_abafb73bda29c4e389edb048a5e5d8d2b}{relabel\+\_\+to\+\_\+front} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)
\begin{DoxyCompactList}\small\item\em relabel\+\_\+to\+\_\+front：最大流的前置重贴标签算法。算法导论26章26.5节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type , typename Action\+Type  = std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type,typename Graph\+Type\+::\+V\+I\+D\+Type)$>$$>$ }\\Graph\+Type\+::\+E\+Weight\+Type \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a2575c09c42d0b30b57702c9379d2fbfb}{kruskal} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, Action\+Type pre\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type, typename Graph\+Type\+::\+V\+I\+D\+Type)\{\}, Action\+Type post\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type, typename Graph\+Type\+::\+V\+I\+D\+Type)\{\})
\begin{DoxyCompactList}\small\item\em kruskal：最小生成树的\+Kruskal算法，算法导论23章23.2节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type , typename Action\+Type  = std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type)$>$$>$ }\\Graph\+Type\+::\+E\+Weight\+Type \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_aba1581358d79ba82dc4fd0c15bc987e6}{prim} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id, Action\+Type pre\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type)\{\}, Action\+Type post\+\_\+action=\mbox{[}$\,$\mbox{]}(typename Graph\+Type\+::\+V\+I\+D\+Type)\{\})
\begin{DoxyCompactList}\small\item\em prim：最小生成树的\+Prim算法，算法导论23章23.2节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a5ed496e8825564d0f9fcfe3b0ac41dec}{initialize\+\_\+single\+\_\+source} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id)
\begin{DoxyCompactList}\small\item\em initialize\+\_\+single\+\_\+source：单源最短路径的初始化操作，算法导论24章24.1节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Vertex\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_afe2bd83fca7df7e07ece9a59b8e7f5a6}{relax} (std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$ from, std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$ to, typename Vertex\+Type\+::\+Key\+Type weight)
\begin{DoxyCompactList}\small\item\em relax：单源最短路径的松弛操作，算法导论24章24.1节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\bool \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_ae96d9b844260ee3ce9225055040c631b}{bellman\+\_\+ford} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id)
\begin{DoxyCompactList}\small\item\em bellman\+\_\+ford：单源最短路径的bellman\+\_\+ford算法，算法导论24章24.1节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_aec7fe196e6aee4c8e6004a05495c8813}{dag\+\_\+shortest\+\_\+path} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id)
\begin{DoxyCompactList}\small\item\em dag\+\_\+shortest\+\_\+path：有向无环图的单源最短路径的dag\+\_\+shortest\+\_\+path算法，算法导论24章24.2节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Graph\+Type $>$ }\\void \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_acac554e111d6377c630865258dd6aa19}{dijkstra} (std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id)
\begin{DoxyCompactList}\small\item\em dijkstra：单源最短路径的dijkstra算法，算法导论24章24.3节 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename T $>$ }\\T \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a19237111c3b1ec2717c5e1aefe2f6d9b}{unlimit} ()
\begin{DoxyCompactList}\small\item\em unlimit：返回正无穷的函数 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename T $>$ }\\bool \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a4f664c13605fc87ca8d26f4aad5a9fa2}{is\+\_\+unlimit} (T t)
\begin{DoxyCompactList}\small\item\em is\+\_\+unlimit：判断是否正无穷 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Vertex\+Type $>$ }\\std\+::vector$<$ typename Vertex\+Type\+::\+V\+I\+D\+Type $>$ \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a1581960f77507024b39572aeb6d1fbd6}{get\+\_\+path} (const std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$ v\+\_\+from, const std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$ v\+\_\+to)
\begin{DoxyCompactList}\small\item\em get\+\_\+path：获取两个顶点之间的路径 \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Matrix\+Type $>$ }\\std\+::string \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm_a97d248a07f1b31df52be3de3b5570237}{matrix\+\_\+string} (const Matrix\+Type \&matrix)
\begin{DoxyCompactList}\small\item\em matrix\+\_\+string：获取矩阵的字符串描述 \end{DoxyCompactList}\end{DoxyCompactItemize}


\subsection{Detailed Description}
Namespace of \hyperlink{namespace_introduction_to_algorithm_1_1_graph_algorithm}{Graph\+Algorithm}. 

该命名空间内包含所有图算法 

\subsection{Function Documentation}
\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_ae96d9b844260ee3ce9225055040c631b}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!bellman\+\_\+ford@{bellman\+\_\+ford}}
\index{bellman\+\_\+ford@{bellman\+\_\+ford}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{bellman\+\_\+ford(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ bool Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::bellman\+\_\+ford (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{source\+\_\+id}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_ae96d9b844260ee3ce9225055040c631b}


bellman\+\_\+ford：单源最短路径的bellman\+\_\+ford算法，算法导论24章24.1节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强指针，必须非空。若为空则抛出异常} & \\
\hline
{\em source\+\_\+id：最小生成树的根结点$<$tt$>$id$<$/tt$>$，必须有效。若无效则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 是否不包含可以从源结点可达的权重为负值的环路。若返回值为true，则说明不包含可以从源结点可达的权重为负值的环路
\end{DoxyReturn}
\subsubsection*{单源最短路径}

单源最短路径问题：给定一个带权重的有向图\+G=(V,E)和权重函数w\+:E-\/$>$R，该权重函数将每条边映射到实数值的权重上。图中一条路径p=$<$v0,v1,...vk$>$的权重 w(p)=w(v0,v1)+w(v1,v2)+...+w(v(k-\/1),vk)。定义结点u到结点v的最短路径权重 delt(u,v)为：


\begin{DoxyItemize}
\item min\{w(p)\+:u--$>$v(通过路径p)\}，如果存在一条从结点u到结点v的路径
\item 正无穷 ，如果不存在一条从结点u到结点v的路径
\end{DoxyItemize}

从结点u到结点v的最短路径定义为任何一条权重w(p)=delt(u,v)的从u到v的路径p。

给定图\+G=(V,E)，对每个结点v我们维持一个前驱结点v.\+pai。在最短路径算法中，由pai值诱导的前驱子图\+G\+\_\+pai=(V\+\_\+pai,E\+\_\+pai)，其中 V\+\_\+pai=\{v属于\+V\+:v.\+pai!=nil\}并上源点s， E\+\_\+pai是\+V\+\_\+pai中所有结点的pai值诱导的边的集合：\+E\+\_\+pai=\{(v.\+pai,v)属于\+E\+:v属于\+V\+\_\+pai-\/\{s\} \}。算法终止时，\+G\+\_\+pai是一棵最短路径树：该树包含了从源结点s 到每个可以从s到达的结点的一条最短路径。

需要指出的是：最短路径不一定是唯一的，最短路径树叶不一定是唯一的。

\subsubsection*{Bellman-\/\+Ford算法}

\paragraph*{算法原理}

Bellman-\/\+Ford算法解决的是一般情况下的单源最短路径问题。在这里边的权重可以为负值。给定带权的有向图\+G=(V,E)和权重函数w\+:E-\/$>$R，\+Bellman-\/\+Ford 算法返回一个bool值，表明是否存在一个从源结点可达的权重为负值的环路。若存在这样的一个环路，算法告诉我们不存在解决方案；若不存在这样的环路， 算法将给出最短路径和它们的权重。

Bellman-\/\+Ford算法通过对边的松弛操作来渐近的降低从源s到每个结点v的最短路径估计值v.key，直到该估计值与实际的最短路径权重相同为止。

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 执行单源最短路径的初始化过程
\item 进行$\vert$\+V$\vert$-\/1次处理，每次处理过程为：对图的每一条边进行一次松弛操作
\item 检查图中是否存在权重为负的环路并返回与之相适应的布尔值
\end{DoxyItemize}

\paragraph*{算法性能}

时间复杂度为\+O(\+V\+E) 

Definition at line 143 of file bellmanford.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a8839165b9e3d4c8c2ccac4cdc28aadd5}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!breadth\+\_\+first\+\_\+search@{breadth\+\_\+first\+\_\+search}}
\index{breadth\+\_\+first\+\_\+search@{breadth\+\_\+first\+\_\+search}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{breadth\+\_\+first\+\_\+search(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type)$>$ pre\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type)\lcurly{}\rcurly{}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type)$>$ post\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type)\lcurly{}\rcurly{})}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::breadth\+\_\+first\+\_\+search (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{source\+\_\+id, }
\item[{std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type)$>$}]{pre\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType)\{\}}, }
\item[{std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type)$>$}]{post\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType)\{\}}}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a8839165b9e3d4c8c2ccac4cdc28aadd5}


breadth\+\_\+first\+\_\+search：广度优先搜索，算法导论22章22.2节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强引用，必须非空。若为空则抛出异常} & \\
\hline
{\em source\+\_\+id：广度优先搜索的源点$<$tt$>$id$<$/tt$>$，必须有效。若无效则抛出异常} & \\
\hline
{\em pre\+\_\+action\+:一个可调用对象，在每次发现一个顶点时调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
{\em post\+\_\+action\+:一个可调用对象，在每次对一个顶点搜索完成时调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+:void
\end{DoxyReturn}
{\ttfamily source\+\_\+id}在以下情况下无效：


\begin{DoxyItemize}
\item {\ttfamily source\+\_\+id}不在区间{\ttfamily \mbox{[}0,N)}之间时，{\ttfamily source\+\_\+id}无效
\item {\ttfamily graph}中不存在某个顶点的{\ttfamily id}等于{\ttfamily source\+\_\+id}时，{\ttfamily source\+\_\+id}无效
\end{DoxyItemize}

广度优先搜索：该算法维护已经发现结点和未发现结点的边界，沿着其广度方向向外扩展。每个结点有三种颜色：白色、灰色、黑色。 白色结点表示未发现；灰色结点表示已发现但是未处理完成；黑色结点表示已处理完成。其中灰色结点就是边界。

给定图 G=(V,E)和一个可以识别的源点{\ttfamily s}。。所有的结点在一开始都被涂上白色。每个结点的颜色存放在属性{\ttfamily color}中； 每个结点的前驱结点放在属性{\ttfamily parent}中。每个结点的属性{\ttfamily key}存放的是从源点到本结点的距离。该算法使用一个先进先出的队列\+Q来管理灰色结点集。


\begin{DoxyItemize}
\item 将所有结点涂为白色，{\ttfamily key}属性设置为正无穷，父结点置为空；
\item 将源点涂为灰色，源点前驱设为空，源点的{\ttfamily key}设为0；
\item 将源点加入队列\+Q中；\+Q中存放的都是已发现但是尚未处理完成的结点
\item 循环直到队列\+Q为空，在循环中执行以下操作：
\begin{DoxyItemize}
\item 取出队列\+Q头部的结点{\ttfamily v}
\item 对结点{\ttfamily v}的邻接表中的白色结点进行发现操作，并将这些结点加入队列\+Q中
\item 对结点{\ttfamily v}染成黑色；
\end{DoxyItemize}
\end{DoxyItemize}

算法的时间复杂度为 O(E+\+V)

最短路径：广度优先搜索能找出给定源结点s到所有可以到达的结点之间的距离。定义从源s到结点v之间的最短路径距离 delt(s,v) 为从结点s到v之间的所有路径里面最少的边数。 如果从s到v没有路径，则 delt(s,v)=正无穷大 。我们定义从s到v之间的长度为 delt(s,v) 的路径为 s 到 v 的最短路径。可以证明：广度优先搜索可以正确计算出最短路径距离。

广度优先树：对于\+G=(V,E)和源点s，定义图\+G的前驱子图为 G\+\_\+pai=(V\+\_\+pai,E\+\_\+pai)，其中 V\+\_\+pai=\{ v属于\+V\+: v.\+parent!=N\+I\+L\}并上\{s\}，\+E\+\_\+pai=\{(v.\+parent,v)\+:v属于(V\+\_\+pai-\/\{s\})\}。 即\+V\+\_\+pai由从源s可达的所有结点组成（包括s本身），\+E\+\_\+pai由\+V\+\_\+pai中去掉s之后的结点的入边组成，其中该入边的对端为结点的父结点。 B\+F\+S算法获取的前驱子图\+G\+\_\+pai包含一条从源结点s到结点v的唯一简单路径，而且该路径也是图\+G里面从源s到v之间的一条最短路径，因此前驱子图也称为广度优先树。 

Definition at line 68 of file bfs.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a31fe8fc6f732112632c51221e739a7d4}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!connected\+\_\+component@{connected\+\_\+component}}
\index{connected\+\_\+component@{connected\+\_\+component}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{connected\+\_\+component(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::connected\+\_\+component (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a31fe8fc6f732112632c51221e739a7d4}


connected\+\_\+component：无向图的连通分量，算法导论21章21.1节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强指针，必须非空。若为空则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+:void
\end{DoxyReturn}
connected\+\_\+component函数使用不相交集合操作来计算一个无向图的连通分量。一旦connected\+\_\+component函数与处理了该图，same\+\_\+component 函数就会回答两个顶点是否在同一个连通分量。

connected\+\_\+component算法步骤：


\begin{DoxyItemize}
\item 将每个顶点v放入它自己的集合中
\item 对每一条边(u,v)，它将包含u和v的集合进行合并
\end{DoxyItemize}

在处理完搜有边之后，两个顶点在相同的连通分量当且仅当与之对应的对象在相同的集合中 

Definition at line 44 of file connectedcomponent.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_acc8cd65d7cf2d584f86cfd92494bdbf4}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!create\+\_\+\+Gf@{create\+\_\+\+Gf}}
\index{create\+\_\+\+Gf@{create\+\_\+\+Gf}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{create\+\_\+\+Gf(const std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::shared\+\_\+ptr$<$Graph\+Type$>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::create\+\_\+\+Gf (
\begin{DoxyParamCaption}
\item[{const std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&}]{flow}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_acc8cd65d7cf2d584f86cfd92494bdbf4}


create\+\_\+\+Gf：根据指定流网络生成一个残余网络。算法导论26章26.2节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em flow} & 一个流 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 残余网络
\end{DoxyReturn}
\subsubsection*{残余网络}

给定网络\+G(\+V,\+E)和流量f，残余网络\+Gf(\+V,\+Ef)由那些仍有空间对流量进行调整的边构成。\+Gf中的顶点就是原图\+G中的顶点。残余网络\+Gf中的边可以由以下组成：


\begin{DoxyItemize}
\item 若(u,v)属于\+E，且f(u,v)$<$c(u,v)，则存在边(u,v)属于\+Ef，且cf(u,v)=c(u,v)-\/f(u,v)，表示沿着该方向图\+G中还能流通cf大小的流量
\item 若(u,v)属于\+E，则存在边(v,u)属于\+Ef,且 cf(v,u)=c(u,v)，表示沿着(u,v)的反方向（即(v,u)方向)可以压入cf大小的反向流量 \begin{quote}
这里f(u,v)为边(u,v)上的流；c(u,v)为图\+G的边(u,v)的容量；cf(u,v)为残余网络\+Gf上的边(u,v)的容量 \end{quote}

\end{DoxyItemize}

这里假定容量c$>$0，一旦容量c=0表示边不存在（禁止流通）；f$>$=0，表示流是正向的。同时假定图中不存在双向边： 图\+G中不可能同时存在边(u,v)以及边(v,u)（即管道是单向的）

要求graph的无效权重为0，否则抛出异常

性能：时间复杂度 O(V+\+E) 

Definition at line 54 of file fordfulkerson.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_ad6a1917551c87991625d8402593ec863}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!create\+\_\+\+L@{create\+\_\+\+L}}
\index{create\+\_\+\+L@{create\+\_\+\+L}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{create\+\_\+\+L(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ {\bf List}$<${\bf List\+Node}$<$typename Graph\+Type\+::\+Vertex\+Type$>$ $>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::create\+\_\+\+L (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{src, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{dst}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_ad6a1917551c87991625d8402593ec863}


create\+\_\+\+L：前置重贴标签算法中的创建\+L链表操作 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em src} & 流的源点，必须有效否则抛出异常 \\
\hline
{\em dst} & 流的汇点，必须有效否则抛出异常 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 初始化的\+L链表
\end{DoxyReturn}
如果src、dst任何一个顶点无效，则抛出异常：


\begin{DoxyItemize}
\item 如果指定的顶点{\ttfamily id}不在{\ttfamily \mbox{[}0,N)}之间，则无效
\item 如果不存在某个顶点与指定的顶点{\ttfamily id}相同，则无效
\end{DoxyItemize}

该操作将所有的除s、t之外的顶点加入到\+L链表中 

Definition at line 113 of file relabeltofront.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_aec7fe196e6aee4c8e6004a05495c8813}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!dag\+\_\+shortest\+\_\+path@{dag\+\_\+shortest\+\_\+path}}
\index{dag\+\_\+shortest\+\_\+path@{dag\+\_\+shortest\+\_\+path}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{dag\+\_\+shortest\+\_\+path(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::dag\+\_\+shortest\+\_\+path (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{source\+\_\+id}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_aec7fe196e6aee4c8e6004a05495c8813}


dag\+\_\+shortest\+\_\+path：有向无环图的单源最短路径的dag\+\_\+shortest\+\_\+path算法，算法导论24章24.2节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强指针，必须非空。若为空则抛出异常} & \\
\hline
{\em source\+\_\+id：最小生成树的根结点$<$tt$>$id$<$/tt$>$，必须有效。若无效则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: void
\end{DoxyReturn}
\subsubsection*{单源最短路径}

单源最短路径问题：给定一个带权重的有向图\+G=(V,E)和权重函数w\+:E-\/$>$R，该权重函数将每条边映射到实数值的权重上。图中一条路径p=$<$v0,v1,...vk$>$的权重 w(p)=w(v0,v1)+w(v1,v2)+...+w(v(k-\/1),vk)。定义结点u到结点v的最短路径权重 delt(u,v)为：


\begin{DoxyItemize}
\item min\{w(p)\+:u--$>$v(通过路径p)\}，如果存在一条从结点u到结点v的路径
\item 正无穷 ，如果不存在一条从结点u到结点v的路径
\end{DoxyItemize}

从结点u到结点v的最短路径定义为任何一条权重w(p)=delt(u,v)的从u到v的路径p。

给定图\+G=(V,E)，对每个结点v我们维持一个前驱结点v.\+pai。在最短路径算法中，由pai值诱导的前驱子图\+G\+\_\+pai=(V\+\_\+pai,E\+\_\+pai)，其中 V\+\_\+pai=\{v属于\+V\+:v.\+pai!=nil\}并上源点s， E\+\_\+pai是\+V\+\_\+pai中所有结点的pai值诱导的边的集合：\+E\+\_\+pai=\{(v.\+pai,v)属于\+E\+:v属于\+V\+\_\+pai-\/\{s\} \}。算法终止时，\+G\+\_\+pai是一棵最短路径树：该树包含了从源结点s 到每个可以从s到达的结点的一条最短路径。

需要指出的是：最短路径不一定是唯一的，最短路径树叶不一定是唯一的。

\subsubsection*{dag\+\_\+shortest\+\_\+path算法}

\paragraph*{算法原理}

dag\+\_\+shortest\+\_\+path算法解决的是有向无环图中的单源最短路径问题。在有向无环图中不存在环路因此也就不存在权重为负值的环路，最短路径都是存在的。 dag\+\_\+shortest\+\_\+path根据结点的拓扑排序次数来对带权重的有向无环图进行边的松弛操作，可以再\+O(V+\+E)时间内计算出单源最短路径。

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 对有向无环图进行拓扑排序
\item 执行单源最短路径的初始化过程
\item 按照顶点的拓扑排序的顺序依次处理，每次处理过程为：对该顶点出发的每一条边进行一次松弛操作
\end{DoxyItemize}

\paragraph*{算法性能}

时间复杂度为\+O(V+\+E) 

Definition at line 71 of file dagshortpath.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a9f44099f26242f50087b3cc16dff965f}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!depth\+\_\+first\+\_\+search@{depth\+\_\+first\+\_\+search}}
\index{depth\+\_\+first\+\_\+search@{depth\+\_\+first\+\_\+search}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{depth\+\_\+first\+\_\+search(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ pre\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type, int)\lcurly{}\rcurly{}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ post\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type, int)\lcurly{}\rcurly{}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ pre\+\_\+root\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type, int)\lcurly{}\rcurly{}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ post\+\_\+root\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type, int)\lcurly{}\rcurly{}, const std\+::vector$<$ typename Graph\+Type\+::\+V\+I\+D\+Type $>$ \&search\+\_\+order=std\+::vector$<$ typename Graph\+Type\+::\+V\+I\+D\+Type $>$())}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::depth\+\_\+first\+\_\+search (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$}]{pre\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType,int)\{\}}, }
\item[{std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$}]{post\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType,int)\{\}}, }
\item[{std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$}]{pre\+\_\+root\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType,int)\{\}}, }
\item[{std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$}]{post\+\_\+root\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType,int)\{\}}, }
\item[{const std\+::vector$<$ typename Graph\+Type\+::\+V\+I\+D\+Type $>$ \&}]{search\+\_\+order = {\ttfamily std\+:\+:vector$<$typename~GraphType\+:\+:VIDType$>$()}}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a9f44099f26242f50087b3cc16dff965f}


depth\+\_\+first\+\_\+search：深度优先搜索，算法导论22章22.3节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强引用，必须非空。若为空则抛出异常} & \\
\hline
{\em pre\+\_\+root\+\_\+action\+:一个可调用对象，在每次发现一个顶点且该顶点是深度优先森林的根节点时调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$以及发现时间$<$tt$>$time$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
{\em post\+\_\+root\+\_\+action\+:一个可调用对象，在每次对一个顶点搜索完成时且该顶点是深度优先森林的根节点时调用调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$以及发现时间$<$tt$>$time$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
{\em pre\+\_\+action\+:一个可调用对象，在每次发现一个顶点时调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$以及发现时间$<$tt$>$time$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
{\em post\+\_\+action\+:一个可调用对象，在每次对一个顶点搜索完成时调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$以及发现时间$<$tt$>$time$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
{\em search\+\_\+order\+:指定搜索顶点的顺序（不同的搜索顺序可能形成的深度优先森林不同)，如果为空则按照顶点的$<$tt$>$id$<$/tt$>$顺序。默认为空} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+:void
\end{DoxyReturn}
深度优先搜索：深度优先搜索总是对最近才发现的结点v的出发边进行搜索，直到该结点的所有出发边都被发现为止。一旦结点v的所有出发边都被发现，则“回溯”到v的前驱结点（v是经过该结点才被发现的）。 该过程一直持续到源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源结点，并重复同样的搜索过程。该算法重复整个过程， 直到图中的所有结点被发现为止。

深度优先搜索维护一个全局的时间。每个结点v有两个时间戳，discover\+\_\+time记录了v第一次被发现的时间（v涂上灰色的时刻）；finish\+\_\+time记录了搜索完成v的相邻结点的时间（v涂上黑色的时刻）。 结点v在v.\+discover\+\_\+time之前为白色，在v.\+discover\+\_\+time之后与v.\+finish\+\_\+time之前为灰色，在v.\+finish\+\_\+time之后为黑色

深度优先搜索步骤：


\begin{DoxyItemize}
\item 初始化：将所有结点染白色，并将它们的父结点置为空(由于\+D\+F\+S\+\_\+\+Vertex构造函数将结点color设为白色，且将父结点置为空，因此在本算法中这个步骤可以省略)
\item 将全局时间 time 置为0
\item 遍历结点集\+V，取出结点v -\/若v是白色的（尚未发现），则调用 visit 操作 \begin{quote}
当这里调用 visit 操作时，结点v会成为一棵树的根

深度优先搜索的结果会依赖于遍历结点集\+V的顺序。不同的遍历顺序得到的结果会不同 \end{quote}

\end{DoxyItemize}

深度优先搜索性能：时间复杂度 O(V+\+E)

深度优先搜索的性质：证明请参考《算法导论》\+:


\begin{DoxyItemize}
\item 深度优先搜索生成的前驱子图\+G\+\_\+pai是一个由多棵树构成的森林
\item 结点 v 是结点 u 在深度优先森林中的后代当且仅当结点v在结点u为灰色的时间段内被发现
\item 结点的发现时间和完成时间具有括号化结构：如果以左括号\char`\"{}(u\char`\"{}来表示结点u被发现，以后括号\char`\"{}u)\char`\"{}表示结点u完成。则发现和完成的历史记载会形成一个规整的表达式。 在深度优先搜索中，对于任意两个结点u和v来说，下面三种情况只有一种成立
\begin{DoxyItemize}
\item 区间\mbox{[}u.\+discover\+\_\+time,u.\+finish\+\_\+time\mbox{]}与区间\mbox{[}v.\+discover\+\_\+time,v.\+finish\+\_\+time\mbox{]}完全分离。 此时在深度优先森林中，结点u不是结点v的后代，结点v也不是结点u的后代
\item 区间\mbox{[}u.\+discover\+\_\+time,u.\+finish\+\_\+time\mbox{]}完全包含在\mbox{[}v.\+discover\+\_\+time,v.\+finish\+\_\+time\mbox{]}，此时在深度优先森林中，结点u是结点v的后代
\item 区间\mbox{[}v.\+discover\+\_\+time,v.\+finish\+\_\+time\mbox{]}完全包含在\mbox{[}u.\+discover\+\_\+time,u.\+finish\+\_\+time\mbox{]}，此时在深度优先森林中，结点v是结点u的后代
\end{DoxyItemize}
\end{DoxyItemize}

深度优先森林的边：对于在图\+G上运行深度优先搜索算法所生成的深度优先森林\+G\+\_\+pai，可以定义四种类型的边：


\begin{DoxyItemize}
\item 树边：它是深度优先森林的边。若结点v是因深度优先算法对边(u,v)的搜索而首先被发现，则(u,v)是一条树边
\item 后向边： 后向边(u,v)将结点u连接到其深度优先树中某个祖先结点v。对于有向图的自循环，自循环被认为是后向边
\item 前向边： 将结点u连接到其在深度优先树中一个后代结点v
\item 横向边： 其他的边。这些边可以连接同一棵深度优先树中的结点（只要其中一个结点不是另外一个结点的祖先），也可以连接不同深度优先树中的两个结点。
\end{DoxyItemize}

在深度优先搜索中，当第一次搜索边(u,v)时：


\begin{DoxyItemize}
\item 若结点v为白色，表明边(u,v)是一条树边
\item 若结点v为灰色，表明边(u,v)是一条后向边
\item 若结点v为黑色，表明边(u,v)是一条前向边或者横向边
\begin{DoxyItemize}
\item 在 u.\+discover\+\_\+time$<$ v.\+discover\+\_\+time 时，为前向边
\item 在 u.\+discover\+\_\+time$<$ v.\+discover\+\_\+time 时，为横向边
\end{DoxyItemize}
\end{DoxyItemize}

在无向图中，每条边要么是树边，要么是后向边。从来不会出现前向边和横向边。 

Definition at line 138 of file dfs.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_acac554e111d6377c630865258dd6aa19}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!dijkstra@{dijkstra}}
\index{dijkstra@{dijkstra}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{dijkstra(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::dijkstra (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{source\+\_\+id}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_acac554e111d6377c630865258dd6aa19}


dijkstra：单源最短路径的dijkstra算法，算法导论24章24.3节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强指针，必须非空。若为空则抛出异常} & \\
\hline
{\em source\+\_\+id：最小生成树的根结点$<$tt$>$id$<$/tt$>$，必须有效。若无效则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: void
\end{DoxyReturn}
\subsubsection*{单源最短路径}

单源最短路径问题：给定一个带权重的有向图\+G=(V,E)和权重函数w\+:E-\/$>$R，该权重函数将每条边映射到实数值的权重上。图中一条路径p=$<$v0,v1,...vk$>$的权重 w(p)=w(v0,v1)+w(v1,v2)+...+w(v(k-\/1),vk)。定义结点u到结点v的最短路径权重 delt(u,v)为：


\begin{DoxyItemize}
\item min\{w(p)\+:u--$>$v(通过路径p)\}，如果存在一条从结点u到结点v的路径
\item 正无穷 ，如果不存在一条从结点u到结点v的路径
\end{DoxyItemize}

从结点u到结点v的最短路径定义为任何一条权重w(p)=delt(u,v)的从u到v的路径p。

给定图\+G=(V,E)，对每个结点v我们维持一个前驱结点v.\+pai。在最短路径算法中，由pai值诱导的前驱子图\+G\+\_\+pai=(V\+\_\+pai,E\+\_\+pai)，其中 V\+\_\+pai=\{v属于\+V\+:v.\+pai!=nil\}并上源点s， E\+\_\+pai是\+V\+\_\+pai中所有结点的pai值诱导的边的集合：\+E\+\_\+pai=\{(v.\+pai,v)属于\+E\+:v属于\+V\+\_\+pai-\/\{s\} \}。算法终止时，\+G\+\_\+pai是一棵最短路径树：该树包含了从源结点s 到每个可以从s到达的结点的一条最短路径。

需要指出的是：最短路径不一定是唯一的，最短路径树叶不一定是唯一的。

\subsubsection*{Dijkstra算法}

\paragraph*{算法原理}

Dijkstra算法解决的是有向图中的单源最短路径问题。\+Dijkstra算法要求所有边的权重都为非负值。

Dijkstra算法核心信息是一组结点集合 S 。从源结点s 到集合 S 中的每一个结点之间的最短路径已经被找到。算法重复从结点集合 V-\/\+S 中选择最短路径估计最小的结点u, 将u加入到集合\+S中，然后对所有从u出发的边进行松弛。本算法利用最小优先队列\+Q来保存结点集合，每个结点的关键字为它的key值。

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 调用 {\ttfamily initialize\+\_\+single\+\_\+source}函数对图的顶点进行初始化
\item 将集合\+S置为空，将所有顶点放入最小优先队列\+Q
\item 循环操作直到\+Q为空，循环内执行以下操作：
\begin{DoxyItemize}
\item 弹出最小优先级队列队首元素u
\item 将u对应的结点放入集合\+S中
\item 对从u出发的边且另一端在\+Q中的边进行松弛。松弛过程隐含着\+Q的一个{\ttfamily decreate\+\_\+key()}方法的调用
\end{DoxyItemize}
\end{DoxyItemize}

\paragraph*{算法性能}

时间复杂度为\+O(V$^\wedge$2+\+E) 

Definition at line 77 of file dijkstra.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a2ae42c12c93664d94b5a6f9980fe8540}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!discharge@{discharge}}
\index{discharge@{discharge}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{discharge(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type u\+\_\+id, std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::discharge (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{u\+\_\+id, }
\item[{std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&}]{flow}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a2ae42c12c93664d94b5a6f9980fe8540}


discharge：最大流的前置重贴标签算法中的释放操作。算法导论26章26.5节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em u\+\_\+id} & 图的顶点id，必须有效否则抛出异常 \\
\hline
{\em flow} & 预流 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: void
\end{DoxyReturn}
如果顶点无效，则抛出异常：


\begin{DoxyItemize}
\item 如果指定的顶点{\ttfamily id}不在{\ttfamily \mbox{[}0,N)}之间，则无效
\item 如果不存在某个顶点与指定的顶点{\ttfamily id}相同，则无效
\end{DoxyItemize}

对于溢出结点u,如果将其所有多余的流通过许可边推送到相邻的结点上，则称该结点得到释放。 在释放过程中，需要对结点u进行重贴标签操作，这使得从结点u发出的边成为许可边。discharge(u) 操作步骤如下：


\begin{DoxyItemize}
\item 循环，条件为u.\+e$>$0，循环内操作为：
\begin{DoxyItemize}
\item 获取u.\+current，假设为v
\item 如果v为空，即遍历到u.\+N链表的末尾，则对u执行relabel操作，然后将u.\+current指向u.\+N链表的头部
\item 如果 v非空，且满足 push 操作的条件(c\+\_\+f(u,v)$>$0且 u.\+h=v.\+h+1)，则执行push操作
\item 如果 v 非空，但不满足 push 操作，则 u.\+current指向u.\+N链表的下一个结点 
\end{DoxyItemize}
\end{DoxyItemize}

Definition at line 53 of file relabeltofront.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a680307505286ae3230d1843c342e874e}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!extend\+\_\+path@{extend\+\_\+path}}
\index{extend\+\_\+path@{extend\+\_\+path}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{extend\+\_\+path(const Matrix\+Type \&\+L, const Matrix\+Type \&\+W)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Matrix\+Type $>$ Matrix\+Type Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::extend\+\_\+path (
\begin{DoxyParamCaption}
\item[{const Matrix\+Type \&}]{L, }
\item[{const Matrix\+Type \&}]{W}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a680307505286ae3230d1843c342e874e}


extend\+\_\+path：扩展一条边，算法导论25章25.1节 


\begin{DoxyParams}{Parameters}
{\em L\+:初始\+L矩阵} & \\
\hline
{\em W} & 图的权重矩阵 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 扩展之后的\+L矩阵
\end{DoxyReturn}
该函数作为 matrix\+\_\+shortest\+\_\+path 的辅助函数 $>$这里要求 Matrix\+Type是一个n$\ast$n的矩阵。如果\+Matrix\+Type不是一个n$\ast$n的矩阵，则编译失败

算法步骤如下：


\begin{DoxyItemize}
\item 外层循环 i 从 0...N-\/1(N次)
\begin{DoxyItemize}
\item 内层循环 j 从 0...N-\/1(N次)
\begin{DoxyItemize}
\item 将new\+L\mbox{[}i\mbox{]}\mbox{[}j\mbox{]}设为正无穷，对所有的k,k 从 0...N-\/1(N次)，选取 L\mbox{[}i\mbox{]}\mbox{[}k\mbox{]}+\+W\mbox{[}k\mbox{]}\mbox{[}j\mbox{]}的最小值赋值给new\+L\mbox{[}i\mbox{]}\mbox{[}j\mbox{]}
\end{DoxyItemize}
\end{DoxyItemize}
\item 最终返回 new\+L
\end{DoxyItemize}

性能：时间复杂度 O(n$^\wedge$3) 

Definition at line 48 of file matrix\+\_\+shortest\+\_\+path.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_ab951caca0797ff2907a180fe81609c70}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!floyd\+\_\+warshall@{floyd\+\_\+warshall}}
\index{floyd\+\_\+warshall@{floyd\+\_\+warshall}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{floyd\+\_\+warshall(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::pair$<$ std\+::array$<$std\+::array$<$typename Graph\+Type\+::\+E\+Weight\+Type ,Graph\+Type\+::\+N\+U\+M$>$,Graph\+Type\+::\+N\+U\+M$>$, std\+::array$<$std\+::array$<$typename Graph\+Type\+::\+E\+Weight\+Type ,Graph\+Type\+::\+N\+U\+M$>$,Graph\+Type\+::\+N\+U\+M$>$ $>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::floyd\+\_\+warshall (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_ab951caca0797ff2907a180fe81609c70}


floyd\+\_\+warshall：返回所有节点对的最短路径的floyd\+\_\+warshall算法。算法导论25章25.2节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定的有向图。它必须非空，否则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 一个n$\ast$n的矩阵(d\+\_\+i\+\_\+j)与n$\ast$n的矩阵(p\+\_\+i\+\_\+j)的std\+::pair，其中 d\+\_\+i\+\_\+j 代表的是结点i到j的一条最短路径的权重, p\+\_\+i\+\_\+j 为从结点i到j的一条最短路径上j的前驱结点
\end{DoxyReturn}
\subsubsection*{所有结点对的最短路径}

给定一个带权重的有向图\+G=(V,E)，其权重函数为w\+:E-\/$>$R，该函数将边映射到实值权重上。我们希望找到对于所有的结点对u,v属于\+V，找出一条从结点u 到结点v的最短路径，以及这条路径的权重。

与单源最短路径不同中使用邻接表来表示图不同，本章的多数算法使用邻接矩阵来表示图。该矩阵代表的是一个有n个结点的有向图\+G=(V,E)的边的权重\+W=(w\+\_\+i\+\_\+j)， 其中 w\+\_\+i\+\_\+j =\+:


\begin{DoxyItemize}
\item 0\+:若i=j
\item 有向边(i,j)的权重，若i!=j且(i,j)属于\+E
\item 正无穷，若 i!=j且(i,j)不属于\+E
\end{DoxyItemize}

我们允许存在负权重的边，目前仍然假定图中不存在权重为负值的环路。

本章讨论的所有结点对最短路径的算法的输出也是一个n$\ast$n的矩阵\+D=(d\+\_\+i\+\_\+j)，其中 d\+\_\+i\+\_\+j 代表的是结点i到j的一条最短路径的权重。

有时候为了解决所有结点对最短路径问题，我们不仅要计算出最短路径权重，还需要计算出前驱结点矩阵 I\+I=(pai\+\_\+i\+\_\+j)，其中 pai\+\_\+i\+\_\+j在i=j或者从i到j 不存在路径时为\+N\+I\+L，在其他情况下给出的是从结点i到结点j的某条最短路径上结点j的前驱结点。由矩阵\+I\+I的第i行所诱导的子图应当是一棵根节点为i 的最短路径树。

\subsubsection*{floyd\+\_\+warshall 算法}

\paragraph*{算法原理}

floyd\+\_\+warshall也是采用一种动态规划算法来解决问题。假定图\+G中的所有结点为\+V=\{1,2,3...n\},考虑其中的一个子集\{1,2,...k\}，这里k是某个小于n的整数。 图中可以存在负权重的边，但是不能存在权重为负的环路。对于任意结点对i,j属于\+V，考虑从结点i到结点j的所有中间结点均取自集合\{1,2,...k\}的路径，并且假设p为其中权重最小的路径。


\begin{DoxyItemize}
\item 若结点k不是路径p的中间结点，则路径p上的所有中间结点都属于集合\{1,2,3,...k-\/1\}。则结点i到j的中间结点取自集合\{1,2,...k-\/1\} 的一条最短路径也是从结点i到j的中间结点取自\{1,2...k)的一条最短路径
\item 若结点k是路径p上的中间结点，则路径p分解为 i--$>$k(经过p1)--$>$j(经过p2)，则路径p1是结点i到k的中间结点取自集合\{1,2...k-\/1\} 的一条最短路径。路径p2是结点k到j的中间结点取自集合\{1,2,...k-\/1\}的一条最短路径。
\end{DoxyItemize}

根据以上观测，设d\+\_\+i\+\_\+j$<$k$>$为从结点i到结点j的所有中间结点全部取自集合\{1,2...k\}的一条最短路径的权重。当k=0时，从结点i到j 的一条不包含编号大于0的中间结点的路径将没有任何中间结点。这样的路径最多只有一条边，因此d\+\_\+i\+\_\+j$<$0$>$=w\+\_\+i\+\_\+j。因此d\+\_\+i\+\_\+j$<$k$>$为：


\begin{DoxyItemize}
\item w\+\_\+i\+\_\+j：当k=0
\item min(d\+\_\+i\+\_\+j$<$k-\/1$>$,d\+\_\+i\+\_\+k$<$k-\/1$>$+d\+\_\+k\+\_\+j$<$k-\/1$>$：当k$>$0
\end{DoxyItemize}

对任何路径来说，所有中间结点都属于集合\{1,2,...n\}，则矩阵\+D$<$n$>$=(d\+\_\+i\+\_\+j$<$n$>$)

我们可以在计算矩阵\+D$<$k$>$的同时计算出前驱矩阵\+I\+I，即计算一个矩阵序列 I\+I$<$0$>$,I\+I$<$1$>$...I\+I$<$k$>$。这里定义\+I\+I$<$k$>$=(pai\+\_\+i\+\_\+j$<$k$>$)， pai\+\_\+i\+\_\+j$<$k$>$为从结点i到j的一条所有中间结点都取自集合\{1,2,...k\}的最短路径上j的前驱结点。

当k=0时，从i到j的一条最短路径没有中间结点，因此 pai\+\_\+i\+\_\+j$<$0$>$=\+:


\begin{DoxyItemize}
\item null\+:若i=j或者w\+\_\+i\+\_\+j=正无穷
\item i ：若i!=j且w\+\_\+i\+\_\+j!=正无穷
\end{DoxyItemize}

对于 k$>$=1，若结点k不是路径p的中间结点，则路径p上的所有中间结点都属于集合\{1,2,3,...k-\/1\}，则 pai\+\_\+i\+\_\+j$<$k$>$=pai\+\_\+i\+\_\+j$<$k-\/1$>$; 若结点k是路径p的中间结点,考虑路径 i--$>$k--$>$j，这里 k!=j，则pai\+\_\+i\+\_\+j$<$k$>$=pai\+\_\+k\+\_\+j$<$k-\/1$>$。因此当k$>$=1时，pai\+\_\+i\+\_\+j$<$k$>$=\+:


\begin{DoxyItemize}
\item pai\+\_\+i\+\_\+j$<$k-\/1$>$：当d\+\_\+i\+\_\+j$<$k-\/1$>$ $<$= d\+\_\+i\+\_\+k$<$k-\/1$>$+dk\+\_\+j$<$k-\/1$>$
\item pai\+\_\+k\+\_\+j$<$k-\/1$>$\+: 当 d\+\_\+i\+\_\+j$<$k-\/1$>$ $>$ d\+\_\+i\+\_\+k$<$k-\/1$>$+dk\+\_\+j$<$k-\/1$>$
\end{DoxyItemize}

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 初始化：从图中获取结果矩阵\+D，以及父矩阵\+P
\item 外层循环 k 从 0..N-\/1(N次)
\begin{DoxyItemize}
\item 新建 D$<$k$>$,P$<$k$>$，同时执行内层循环 i 从 0..N-\/1(N次)
\item 执行最内层循环 j 从 0..N-\/1(N次)
\begin{DoxyItemize}
\item 根据递推公式对d\+\_\+i\+\_\+j$<$k$>$和p\+\_\+i\+\_\+j$<$k$>$赋值(此时\+D等于\+D$<$k-\/1$>$，\+P等于\+P$<$k-\/1$>$
\end{DoxyItemize}
\item 将\+D$<$k$>$赋值给\+D,P$<$k$>$赋值给\+P
\end{DoxyItemize}
\item 返回 std\+::make\+\_\+pair(\+D,\+P)
\end{DoxyItemize}

\paragraph*{算法性能}

时间复杂度 O(\+V$^\wedge$3) 

Definition at line 109 of file floyd\+\_\+warshall.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a23a29754883e1edd7bd95a76634444a2}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!ford\+\_\+fulkerson@{ford\+\_\+fulkerson}}
\index{ford\+\_\+fulkerson@{ford\+\_\+fulkerson}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{ford\+\_\+fulkerson(const std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::array$<$std\+::array$<$typename Graph\+Type\+::\+E\+Weight\+Type,Graph\+Type\+::\+N\+U\+M$>$,Graph\+Type\+::\+N\+U\+M$>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::ford\+\_\+fulkerson (
\begin{DoxyParamCaption}
\item[{const std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{src, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{dst}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a23a29754883e1edd7bd95a76634444a2}


ford\+\_\+fulkerson：最大流的ford\+\_\+fulkerson算法。算法导论26章26.2节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em src} & 流的源点，必须有效否则抛出异常 \\
\hline
{\em dst} & 流的汇点，必须有效否则抛出异常 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 最大流矩阵
\end{DoxyReturn}
如果src、dst任何一个顶点无效，则抛出异常：


\begin{DoxyItemize}
\item 如果指定的顶点{\ttfamily id}不在{\ttfamily \mbox{[}0,N)}之间，则无效
\item 如果不存在某个顶点与指定的顶点{\ttfamily id}相同，则无效
\end{DoxyItemize}

\subsubsection*{最大流}

流网络\+G=（\+V,E）是一个有向图，图中每条边(u,v)属于\+E都有一个正的容量值c(u,v)$>$0。而且如果边集合\+E中包含一条边(u,v)，则图中不存在反向边 (v,u)。为方便起见，假设(u,v)不属于\+E,定义c(u,v)=0（即无效权重为0），并且在图中不允许自循环。

在流网络中存在两个特殊点：源结点s和汇点t。假定每一个结点都在从源点s到汇点t的某条路径上。即对于每个结点v属于\+E，存在某条路径 s--$>$v--$>$t。

G中的流是一个实值函数f\+:V$\ast$\+V--$>$R，满足下面两条性质：


\begin{DoxyItemize}
\item 容量限制：对于所有结点u,v属于\+V，要求0$<$= f(u,v) $<$= c(u,v)
\item 流量守恒： 对于所有结点u属于\+V-\/\{s,t\}，要求：从u进入的流等于从u出去的流
\end{DoxyItemize}

对于(u,v)不属于\+E的情况，从结点u到v之间没有流，因此f(u,v)=0。我们称非负数值f(u,v)为从结点u到v的流。一个流f的值 $\vert$f$\vert$=从源点流出的总流量-\/ 流入源结点的总流量

最大流问题：给定流网络\+G、一个源结点s、一个汇点t,找出值最大的一个流

\subsubsection*{ford\+\_\+fulkerson算法}

\paragraph*{算法原理}

ford\+\_\+fulkerson 算法更准确的称呼是一种方法而不是算法，因为它包含了几种运行时间各不相同的具体实现。 它依赖于三种重要思想：残余网络、增广路径和切割。

\subparagraph*{残余网络}

给定流网络\+G(\+V,\+E)和流量f，残余网络\+Gf(\+V,\+Ef)由那些仍有空间对流量进行调整的边构成。 Gf中的顶点就是原图\+G中的顶点。残余网络\+Gf中的边可以由以下组成：


\begin{DoxyItemize}
\item 若(u,v)属于\+E，且f(u,v)$<$c(u,v)，则存在边(u,v)属于\+Ef，且cf(u,v)=c(u,v)-\/f(u,v)，表示沿着该方向图\+G中还能流通cf大小的流量
\item 若(u,v)属于\+E，则存在边(v,u)属于\+Ef,且 cf(v,u)=c(u,v)，表示沿着(u,v)的反方向（即(v,u)方向)可以压入cf大小的反向流量 \begin{quote}
这里f(u,v)为边(u,v)上的流；c(u,v)为图\+G的边(u,v)的容量；cf(u,v)为残余网络\+Gf上的边(u,v)的容量 \end{quote}

\end{DoxyItemize}

\subparagraph*{增广路径}

给定流网络\+G=(V,E)和流f，增广路径p是残余网络\+Gf中一条源结点s到汇点t的简单路径。我们称一条增广路径 p上能够为每条边增加的流量的最大值为路径p的残余容量，定义为 cf(p)= min \{cf(u,v)\+:(u,v)属于路径p\}

\subparagraph*{最大流和最小切割定理}

流网络\+G=(V,E)的一个切割(\+S,\+T)是将结点集合\+V划分为\+S和\+T=V-\/\+S两个集合，使得s属于\+S，t属于\+T。切割(S,T) 的容量c(\+S,\+T)=c(u,v)的累加，其中u属于\+S,v属于\+T

设f为流网络\+G=(V,E)中的一个流，该流网络的源点为s，汇点为t，则下面的条件是等价的：


\begin{DoxyItemize}
\item f是\+G的一个最大流
\item 残余网络\+Gf不包括任何增广路径
\item $\vert$f$\vert$=c(\+S,\+T)，其中(\+S,\+T)是流网络\+G的某个切割
\end{DoxyItemize}

\paragraph*{算法步骤}

ford\+\_\+fulkerson算法循环增加流的值。在开始的时候对于所有的结点u,v属于\+V，f(u,v)=0。在每一轮迭代中， 我们将图\+G的流值进行增加，方法就是在\+G的残余网络\+Gf中寻找一条增广路径。算法步骤如下：


\begin{DoxyItemize}
\item 初始化： 创建流矩阵flow，flow\mbox{[}i\mbox{]}\mbox{[}j\mbox{]}均初始化为0
\item 循环迭代：
\begin{DoxyItemize}
\item 根据flow和\+G创建残余网络\+Gf，寻找增广路径
\item 若增广路径不存在，则跳出迭代，证明现在的流就是最大流
\item 若增广路径存在，则更新流矩阵。更新方法为：
\begin{DoxyItemize}
\item 取出增广路径的残余容量 cf(p)= min \{cf(u,v)\+:(u,v)属于路径p\}，然后更新增广路径p中的边(u,v)：
\begin{DoxyItemize}
\item 若(u,v)属于图\+G的边\+E，则 flow\mbox{[}u\mbox{]}\mbox{[}v\mbox{]}=flow\mbox{[}u\mbox{]}\mbox{[}v\mbox{]}+cf(p)
\item 若(v,u)属于图\+G的边\+E，则 flow\mbox{[}u\mbox{]}\mbox{[}v\mbox{]}=flow\mbox{[}u\mbox{]}\mbox{[}v\mbox{]}-\/cf(p)
\end{DoxyItemize}
\end{DoxyItemize}
\end{DoxyItemize}
\item 返回流矩阵 flow
\end{DoxyItemize}

\paragraph*{算法性能}

ford\+\_\+fulkerson算法运行时间取决于如何寻找增广路径。如果选择不好，算法可能不会终止：流的值会随着后续的递增而增加， 但是它却不一定收敛于最大的流值。如果用广度优先搜索来寻找增广路径，算法的运行时间将会是多项式数量级。

假定最大流问题中的容量均为整数，由于流量值每次迭代中最少增加一个单位，因此算法运行时间为 O(E$\vert$f$\ast$$\vert$) ,$\vert$f$\ast$$\vert$为最大流的值 

Definition at line 178 of file fordfulkerson.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_ab134ec014d01e25ec2ed7d2c97babe23}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!generic\+\_\+push\+\_\+relabel@{generic\+\_\+push\+\_\+relabel}}
\index{generic\+\_\+push\+\_\+relabel@{generic\+\_\+push\+\_\+relabel}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{generic\+\_\+push\+\_\+relabel(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::array$<$std\+::array$<$typename Graph\+Type\+::\+E\+Weight\+Type,Graph\+Type\+::\+N\+U\+M$>$,Graph\+Type\+::\+N\+U\+M$>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::generic\+\_\+push\+\_\+relabel (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{src, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{dst}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_ab134ec014d01e25ec2ed7d2c97babe23}


generic\+\_\+push\+\_\+relabel：最大流的推送-\/重贴标签算法。算法导论26章26.4节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em src} & 流的源点，必须有效否则抛出异常 \\
\hline
{\em dst} & 流的汇点，必须有效否则抛出异常 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 最大流矩阵
\end{DoxyReturn}
如果src、dst任何一个顶点无效，则抛出异常：


\begin{DoxyItemize}
\item 如果指定的顶点{\ttfamily id}不在{\ttfamily \mbox{[}0,N)}之间，则无效
\item 如果不存在某个顶点与指定的顶点{\ttfamily id}相同，则无效
\end{DoxyItemize}

\subsubsection*{最大流}

流网络\+G=（\+V,E）是一个有向图，图中每条边(u,v)属于\+E都有一个正的容量值c(u,v)$>$0。而且如果边集合\+E中包含一条边(u,v)，则图中不存在反向边 (v,u)。为方便起见，假设(u,v)不属于\+E,定义c(u,v)=0（即无效权重为0），并且在图中不允许自循环。

在流网络中存在两个特殊点：源结点s和汇点t。假定每一个结点都在从源点s到汇点t的某条路径上。即对于每个结点v属于\+E，存在某条路径 s--$>$v--$>$t。

G中的流是一个实值函数f\+:V$\ast$\+V--$>$R，满足下面两条性质：


\begin{DoxyItemize}
\item 容量限制：对于所有结点u,v属于\+V，要求0$<$= f(u,v) $<$= c(u,v)
\item 流量守恒： 对于所有结点u属于\+V-\/\{s,t\}，要求：从u进入的流等于从u出去的流
\end{DoxyItemize}

对于(u,v)不属于\+E的情况，从结点u到v之间没有流，因此f(u,v)=0。我们称非负数值f(u,v)为从结点u到v的流。一个流f的值 $\vert$f$\vert$=从源点流出的总流量-\/ 流入源结点的总流量

最大流问题：给定流网络\+G、一个源结点s、一个汇点t,找出值最大的一个流

\subsubsection*{generic\+\_\+push\+\_\+relabel 算法}

\paragraph*{算法原理}

目前最大流的最快实现是基于推送-\/重贴标签算法。推送-\/重贴标签算法比 Ford-\/fulkserson的局域性更强。它不是对整个残余网络进行检查， 而是一个结点一个结点的查看，每一步只检查当前结点的邻结点。与 Ford-\/fulkerson 方法不同， 推送-\/重贴标签算法并不在整个执行过程中保持流量守恒性质，而是维持一个预流，该流是一个 V$\ast$\+V --$>$ R的函数f,它满足容量限制单不满足流量守恒性质。 进入一个点的流量可以超过流出该结点的流量，我们称结点u的 （进入流量-\/流出流量）=e(u)为结点u的超额流。 对于结点u属于\+V-\/\{s,t\}，如果 e(u)$>$0，则称结点u溢出。

考虑一个流网络\+G=(V,E)，我们将有向边看作管道，连接管道的结点有两个性质：


\begin{DoxyItemize}
\item 为了容纳额外的流e，每个结点都隐藏有一个外流的管道，该管道通向一个容量无穷大的水库
\item 每个结点都有一个高度h，高度的值随着算法的推进而增加
\end{DoxyItemize}

高度h满足下面性质：h(s)=$\vert$\+V$\vert$,h(t)=0,对于所有的边(u,v)属于\+E\+\_\+f（残余网络中的边），则有 h(u)$<$=h(v)+1

结点的高度h决定了流的推送方向：我们只从高处向低处push流。我们将源的高度固定在$\vert$\+V$\vert$，将汇点的高度固定在0。其他结点的高度初始时为0， 但是随着时间的推移而不断增加。

generic\+\_\+push\+\_\+relabel算法首先从源结点往下发送尽可能多的流到汇点，发送的流量为源结点所发出的所有管道的流量之和。 当流进入一个中间结点时，他们被收集在该结点的水库中。

算法过程中，可能发现所有离开结点u的未充满的管道高度都比u大或者和u相等。此时为了消除结点u的超额流量，必须增加结点u的高度。 这就是“重贴标签”操作，我们将结点u的高度增加到比其最低的邻居结点的高度多1个单位的高度，这里要求结点u到该邻居结点的管道必须未充满。 因此在执行重贴标签后，一个结点u至少有一个流出管道。可以通过它推送更多的流。

最终一旦所有水库为空，则预流不但是“合法”的流，也是一个最大流。

\paragraph*{基本操作}

\subparagraph*{push 操作}

如果一个结点 u是一个溢出结点，则至少有一条入边，假设为(v,u)，且f(v,u)$>$0。此时残留网络\+G\+\_\+f中的边c\+\_\+f(u,v)$>$0。如果此时还有h(u)=h(v)+1， 则可以对边(u,v)执行push操作。

因为结点u有一个正的超额流u.\+e，且边(u,v)的残余容量为正，因此可以增加结点u到v的流，增加的幅度为min(u.\+e,c\+\_\+f(u,v))，这种幅度的增加不会导致 u.\+e为负值或者容量 c(u,v) 被突破

push操作步骤：


\begin{DoxyItemize}
\item 计算残余容量 c\+\_\+f(u,v)
\item 计算流的增加幅度 delt\+\_\+f=min(u.\+e,c\+\_\+f(u,v))
\item 更新流：
\begin{DoxyItemize}
\item 如果 (u,v) 属于 E，则 f(u,v) += delt\+\_\+f
\item 如果 (v,u) 属于 E，则 f(v,u) -\/= delt\+\_\+f
\end{DoxyItemize}
\item 更新溢出流量：
\begin{DoxyItemize}
\item u.\+e -\/= delt(u,v)
\item v.\+e += delt(u,v)
\end{DoxyItemize}
\end{DoxyItemize}

\subparagraph*{relabel 操作}

如果结点u溢出，并且对于所有边(u,v)属于\+E\+\_\+f(残留网络\+G\+\_\+f中的边)，有u.\+h$<$=v.\+h，则可以对结点u执行relabel操作。 当调用relabel操作时，\+E\+\_\+f必须包含至少一条从结点u出发的边。

relabel 步骤：


\begin{DoxyItemize}
\item 计算 min\{v.\+h\+:(u,v)属于\+E\+\_\+f\}
\item u.\+h=1+ min\{v.\+h\+:(u,v)属于\+E\+\_\+f\}
\end{DoxyItemize}

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 初始化操作：
\begin{DoxyItemize}
\item 初始化预流 flow\+: flow(u,v)=c(u,v)如果u=s;否则 flow(u,v)=0
\item 初始化高度函数 h\+: h(s)=$\vert$\+V$\vert$;h(u)=0, u属于 V-\/\{s\}
\item 初始化超额流量 e： e(u)=c(s,u)，u为与源s相邻的结点; e(u)=0，u为与源s不相邻的结点; e(s)初始化为所有s出发的管道之后的相反数
\end{DoxyItemize}
\item 执行循环，直到所有结点u属于\+V-\/\{s,t\}不存在超额流量e为止。循环内执行：
\begin{DoxyItemize}
\item 如果可以执行 push 操作，则执行push操作
\item 如果不能执行 push 操作，又由于存在超额流量 e$>$0 的结点，因此必然可以执行 relabel 操作。则执行 relabel 操作
\end{DoxyItemize}
\end{DoxyItemize}

\paragraph*{算法性能}

算法性能：时间复杂度 O(\+V$^\wedge$2 E) 

Definition at line 373 of file genericpushrelabel.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a1581960f77507024b39572aeb6d1fbd6}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!get\+\_\+path@{get\+\_\+path}}
\index{get\+\_\+path@{get\+\_\+path}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{get\+\_\+path(const std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$ v\+\_\+from, const std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$ v\+\_\+to)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Vertex\+Type $>$ std\+::vector$<$typename Vertex\+Type\+::\+V\+I\+D\+Type$>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::get\+\_\+path (
\begin{DoxyParamCaption}
\item[{const std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$}]{v\+\_\+from, }
\item[{const std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$}]{v\+\_\+to}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a1581960f77507024b39572aeb6d1fbd6}


get\+\_\+path：获取两个顶点之间的路径 


\begin{DoxyParams}{Parameters}
{\em v\+\_\+from} & 起始顶点 \\
\hline
{\em v\+\_\+to} & 终止顶点 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 两个顶点之间的路径包含的顶点的{\ttfamily id}序列
\end{DoxyReturn}
获取从{\ttfamily v\+\_\+from}到{\ttfamily v\+\_\+to}之间的一条路径，该路径用途经的顶点的{\ttfamily id}来表示，是一个{\ttfamily std\+::vector$<$typename Vertex\+Type\+::\+V\+I\+D\+Type$>$}类型。

要求{\ttfamily v\+\_\+from}与{\ttfamily v\+\_\+to}非空，否则抛出异常 

Definition at line 141 of file header.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a267d39a5bb09200f37a1cd2f0ad4f69f}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!graph\+\_\+plus\+\_\+1v@{graph\+\_\+plus\+\_\+1v}}
\index{graph\+\_\+plus\+\_\+1v@{graph\+\_\+plus\+\_\+1v}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{graph\+\_\+plus\+\_\+1v(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::shared\+\_\+ptr$<${\bf Graph}$<$Graph\+Type\+::\+N\+U\+M+1,typename Graph\+Type\+::\+Vertex\+Type$>$ $>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::graph\+\_\+plus\+\_\+1v (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a267d39a5bb09200f37a1cd2f0ad4f69f}


graph\+\_\+plus\+\_\+1v：根据图graph生成一个新图。算法导论25章25.2节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定的有向图。它必须非空，否则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 一个新图
\end{DoxyReturn}
根据图graph生成一个新图new\+\_\+graph。new\+\_\+graph的顶点 graph的顶点加上一个新顶点s； new\+\_\+graph的边为graph的边加上\{(s,v)\+:v属于graph的顶点\}; new\+\_\+graph的边的权重为graph的边权重，以及 w(s,v)=0 $>$注意：设原图有\+N个顶点，则新图有\+N+1个顶点

本函数是 johnson 算法的辅助函数 

Definition at line 46 of file johnson.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_af1dfc9c1874850fb1415db3644497777}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!initial\+\_\+vertex\+\_\+\+N\+List@{initial\+\_\+vertex\+\_\+\+N\+List}}
\index{initial\+\_\+vertex\+\_\+\+N\+List@{initial\+\_\+vertex\+\_\+\+N\+List}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{initial\+\_\+vertex\+\_\+\+N\+List(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::initial\+\_\+vertex\+\_\+\+N\+List (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{src, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{dst}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_af1dfc9c1874850fb1415db3644497777}


initial\+\_\+vertex\+\_\+\+N\+List：前置重贴标签算法中的初始化邻接链表操作 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em src} & 流的源点，必须有效否则抛出异常 \\
\hline
{\em dst} & 流的汇点，必须有效否则抛出异常 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: void
\end{DoxyReturn}
如果src、dst任何一个顶点无效，则抛出异常：


\begin{DoxyItemize}
\item 如果指定的顶点{\ttfamily id}不在{\ttfamily \mbox{[}0,N)}之间，则无效
\item 如果不存在某个顶点与指定的顶点{\ttfamily id}相同，则无效
\end{DoxyItemize}

该操作将初始化除了s、t之外所有顶点的邻接链表 

Definition at line 153 of file relabeltofront.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_aeaf3e258f5ae9aed76158255fa603c00}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!initialize\+\_\+preflow@{initialize\+\_\+preflow}}
\index{initialize\+\_\+preflow@{initialize\+\_\+preflow}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{initialize\+\_\+preflow(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::initialize\+\_\+preflow (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{src, }
\item[{std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&}]{flow}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_aeaf3e258f5ae9aed76158255fa603c00}


initialize\+\_\+preflow：generic\+\_\+push\+\_\+relabel算法的初始化操作。算法导论26章26.4节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em src} & 流的源点，必须有效否则抛出异常 \\
\hline
{\em flow} & 预流的引用（执行过程中会更新预流） \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: void
\end{DoxyReturn}
如果src无效，则抛出异常：


\begin{DoxyItemize}
\item 如果指定的顶点{\ttfamily id}不在{\ttfamily \mbox{[}0,N)}之间，则无效
\item 如果不存在某个顶点与指定的顶点{\ttfamily id}相同，则无效
\end{DoxyItemize}

初始化操作执行下列操作：


\begin{DoxyItemize}
\item 初始化预流 flow\+: flow(u,v)=c(u,v)如果u=s;否则 flow(u,v)=0
\item 初始化高度函数 h\+: h(s)=$\vert$\+V$\vert$;h(u)=0, u属于 V-\/\{s\}
\item 初始化超额流量 e： e(u)=c(s,u)，u为与源s相邻的结点; e(u)=0，u为与源s不相邻的结点; e(s)初始化为所有s出发的管道之后的相反数 \begin{quote}
由顶点的{\ttfamily key}属性存储超额流量e\end{quote}

\end{DoxyItemize}

Definition at line 227 of file genericpushrelabel.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a5ed496e8825564d0f9fcfe3b0ac41dec}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!initialize\+\_\+single\+\_\+source@{initialize\+\_\+single\+\_\+source}}
\index{initialize\+\_\+single\+\_\+source@{initialize\+\_\+single\+\_\+source}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{initialize\+\_\+single\+\_\+source(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::initialize\+\_\+single\+\_\+source (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{source\+\_\+id}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a5ed496e8825564d0f9fcfe3b0ac41dec}


initialize\+\_\+single\+\_\+source：单源最短路径的初始化操作，算法导论24章24.1节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强指针，必须非空。若为空则抛出异常} & \\
\hline
{\em source\+\_\+id：最小生成树的根结点$<$tt$>$id$<$/tt$>$，必须有效。若无效则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: void
\end{DoxyReturn}
{\ttfamily source\+\_\+id}在以下情况下无效：


\begin{DoxyItemize}
\item {\ttfamily source\+\_\+id}不在区间{\ttfamily \mbox{[}0,N)}之间时，{\ttfamily source\+\_\+id}无效
\item {\ttfamily graph}中不存在某个顶点的{\ttfamily id}等于{\ttfamily source\+\_\+id}时，{\ttfamily source\+\_\+id}无效
\end{DoxyItemize}

单源最短路径的初始化操作将所有的结点的{\ttfamily key}设置为正无穷，将所有结点的{\ttfamily parent}设为空。然后将源结点的{\ttfamily key}设为0。

性能：时间复杂度\+O(\+V) 

Definition at line 43 of file bellmanford.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a4f664c13605fc87ca8d26f4aad5a9fa2}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!is\+\_\+unlimit@{is\+\_\+unlimit}}
\index{is\+\_\+unlimit@{is\+\_\+unlimit}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{is\+\_\+unlimit(\+T t)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename T $>$ bool Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::is\+\_\+unlimit (
\begin{DoxyParamCaption}
\item[{T}]{t}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a4f664c13605fc87ca8d26f4aad5a9fa2}


is\+\_\+unlimit：判断是否正无穷 


\begin{DoxyParams}{Parameters}
{\em t} & 待判断的数 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 如果该数是正无穷大，则返回{\ttfamily true}，否则返回{\ttfamily false}
\end{DoxyReturn}
将本函数判断一个数是否正无穷；若是则返回true;若不是则返回false

这里将大于等于{\ttfamily std\+::numeric\+\_\+limits$<$T$>$\+::max()/3}的数判断结果为正无穷 $>$因为考虑到正无穷减去一个数必须保证结果也是正无穷 

Definition at line 126 of file header.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a856b132d068d0553355203a16cdec97d}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!johnson@{johnson}}
\index{johnson@{johnson}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{johnson(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::array$<$std\+::array$<$typename Graph\+Type\+::\+E\+Weight\+Type ,Graph\+Type\+::\+N\+U\+M$>$,Graph\+Type\+::\+N\+U\+M$>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::johnson (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a856b132d068d0553355203a16cdec97d}


johnson：返回所有节点对的最短路径的johnson算法。算法导论25章25.3节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定的有向图。它必须非空，否则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 一个n$\ast$n的矩阵(d\+\_\+i\+\_\+j)，其中 d\+\_\+i\+\_\+j 代表的是结点i到j的一条最短路径的权重
\end{DoxyReturn}
\subsubsection*{所有结点对的最短路径}

给定一个带权重的有向图\+G=(V,E)，其权重函数为w\+:E-\/$>$R，该函数将边映射到实值权重上。我们希望找到对于所有的结点对u,v属于\+V，找出一条从结点u 到结点v的最短路径，以及这条路径的权重。

与单源最短路径不同中使用邻接表来表示图不同，本章的多数算法使用邻接矩阵来表示图。该矩阵代表的是一个有n个结点的有向图\+G=(V,E)的边的权重\+W=(w\+\_\+i\+\_\+j)， 其中 w\+\_\+i\+\_\+j =\+:


\begin{DoxyItemize}
\item 0\+:若i=j
\item 有向边(i,j)的权重，若i!=j且(i,j)属于\+E
\item 正无穷，若 i!=j且(i,j)不属于\+E
\end{DoxyItemize}

我们允许存在负权重的边，目前仍然假定图中不存在权重为负值的环路。

本章讨论的所有结点对最短路径的算法的输出也是一个n$\ast$n的矩阵\+D=(d\+\_\+i\+\_\+j)，其中 d\+\_\+i\+\_\+j 代表的是结点i到j的一条最短路径的权重。

有时候为了解决所有结点对最短路径问题，我们不仅要计算出最短路径权重，还需要计算出前驱结点矩阵 I\+I=(pai\+\_\+i\+\_\+j)，其中 pai\+\_\+i\+\_\+j在i=j或者从i到j 不存在路径时为\+N\+I\+L，在其他情况下给出的是从结点i到结点j的某条最短路径上结点j的前驱结点。由矩阵\+I\+I的第i行所诱导的子图应当是一棵根节点为i 的最短路径树。

\subsubsection*{Johnson算法}

\paragraph*{算法原理}

对于稀疏图来说\+Johnson算法的渐近表现要优于重复平方法和\+Floyd-\/\+Warshall算法。\+Johnson算法要么返回一个包含所有结点对的最短路径权重的矩阵， 要么报告输入图中包含一个权重为负值的环路。\+Johnson算法在运行中需要使用\+Dijkstra算法和\+Bellman-\/\+Ford算法作为自己的子程序。

Johnson算法使用一种称为重赋权重的技术。若图\+G=(V,E)中所有边权重w都为非负值，则可以通过对每一对顶点运行一次\+Dijkstra 算法来找到所有顶点对直接的最短路径。如果图\+G包含负权重的边，但没有权重为负值的环路，则需要计算出一组新的非负权重值，然后用同样的方法。 新赋的权重w\textquotesingle{}要求满足一下性质：


\begin{DoxyItemize}
\item 对于所有结点对u,v属于\+V，一条路径p实在使用权重函数w时从u到v的一条最短路径，当且仅当p实在使用权重函数w\textquotesingle{} 时从u到v的一条最短路径
\item 对于所有的边(u,v)，新权重w\textquotesingle{}(u,v)非负
\end{DoxyItemize}

对于给定的有向图\+G=(V,E)，权重函数w：\+E-\/$>$R 。我们制作一副新图\+G\textquotesingle{}=(V\textquotesingle{},E\textquotesingle{})，其中\+V\textquotesingle{}=V并上\{s\}，s是一个新结点，s不属于\+V。 E\textquotesingle{}=E并上\{(s,v);v属于\+V\}。我们对权重函数w进行扩展，使得对于所有结点v属于\+V，有w(s,v)=0。 对所有的结点v属于\+V\textquotesingle{}，我们定义h(v)=delt(s,v)。定义w\textquotesingle{}(u,v)=w(u,v)+h(u)-\/h(v)

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 重赋权重：
\begin{DoxyItemize}
\item 创建新图 new\+\_\+graph
\item 对新图执行 bellman\+\_\+ford 的调用，源点为新创建的结点s
\item 如果有负权值的环路，则抛出异常。
\item 如果没有负权重环路，则创建h函数，并对new\+\_\+graph中的所有边执行重新赋权
\end{DoxyItemize}
\item 在 new\+\_\+graph上，除了新的顶点s之外的所有顶点v,以v为源顶点执行dijkstra过程。\+D\mbox{[}i\mbox{]}\mbox{[}j\mbox{]}等于 new\+\_\+graph 中以i为源点到j的最短路径的权重的修正值， 修正的方法就是重新赋权的逆过程。
\item 返回矩阵 D
\end{DoxyItemize}

\paragraph*{算法性能}

时间复杂度 O（\+V$^\wedge$2 lg\+V + V\+E) 

Definition at line 139 of file johnson.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a2575c09c42d0b30b57702c9379d2fbfb}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!kruskal@{kruskal}}
\index{kruskal@{kruskal}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{kruskal(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, Action\+Type pre\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type, typename Graph\+Type\+::\+V\+I\+D\+Type)\lcurly{}\rcurly{}, Action\+Type post\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type, typename Graph\+Type\+::\+V\+I\+D\+Type)\lcurly{}\rcurly{})}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type , typename Action\+Type  = std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type,typename Graph\+Type\+::\+V\+I\+D\+Type)$>$$>$ Graph\+Type\+::\+E\+Weight\+Type Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::kruskal (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{Action\+Type}]{pre\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType,typename~GraphType\+:\+:VIDType)\{\}}, }
\item[{Action\+Type}]{post\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType,typename~GraphType\+:\+:VIDType)\{\}}}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a2575c09c42d0b30b57702c9379d2fbfb}


kruskal：最小生成树的\+Kruskal算法，算法导论23章23.2节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强指针，必须非空。若为空则抛出异常} & \\
\hline
{\em source\+\_\+id：最小生成树的根结点$<$tt$>$id$<$/tt$>$，必须有效。若无效则抛出异常} & \\
\hline
{\em pre\+\_\+action\+:一个可调用对象，在每次从最小优先级队列中弹出最小顶点时立即调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
{\em post\+\_\+action\+:一个可调用对象，在每次从最小优先级队列中弹出最小顶点并处理完它的边时立即调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 最小生成树的权重
\end{DoxyReturn}
\subsubsection*{最小生成树}

最小生成树：对于一个连通无向图\+G=(V,E)，对于每一条边(u,v)属于\+E都赋予了一个权重w(u,v)。我们希望找出一个无环子集\+T，其中\+T为\+E的子集，使得所有的顶点\+V位于\+T中， 同时\+T具有最小的权重。由于\+T是无环的，且连通所有结点因此\+T必然是一棵树。我们称这样的树为生成树。称从\+G中求取该生成树的问题为最小生成树问题。

通用的最小生成树使用贪心策略。该策略在每个时刻找到最小生成树的一条边，并在整个策略过程中维持循环不变式：边的集合\+A在每次循环之前是某棵最小生成树的一个子集。

在每一步，选择一条边(u,v)，将其加入集合\+A中，使得\+A不违反循环不变式。称这样的边(u,v)为边集合\+A的安全边。

\subsubsection*{Kruskal 算法}

\paragraph*{算法原理}

在\+Kruskal算法中集合\+A是一个森林，其结点就是\+G的结点。\+Kruskal算法找到安全边的办法是：在所有连接森林中两棵不同树的边里面，找到权重最小的边(u,v)。 Kruskal算法使用一个不相交集合数据结构来维护几个互不相交的元素集合。每个集合代表当前森林中的一棵树

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 初始化：将集合\+A置为空；对\+G中的每一个结点v,以它为根构造一棵单根树
\item 将\+G中的边\+E按照权重单调递增的顺序排序
\item 循环挑选\+E中的(u,v)，按照单调增的顺序。在循环内执行：
\begin{DoxyItemize}
\item 如果u所在的树不等于v所在的树，则将(u,v)加入\+A中，并且合并u所在的树与v所在的树
\end{DoxyItemize}
\end{DoxyItemize}

$>$根据算法的特征，如果图中只有一个顶点，算法得到的集合\+A为空集；但是实际上集合\+A应该包含该顶点。这是算法在极端情况下的\+B\+U\+G。

\paragraph*{算法性能}

Kruskal算法运行时间依赖于不相交集合数据结构的实现方式。如果采用算法导论21.3节讨论的不相交集合森林实现（也是我在src/set\+\_\+algorithms/disjoint\+\_\+set中实现的）， 则\+Kruskal算法的时间为 O(\+Elg\+V) 

Definition at line 69 of file kruskal.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_ab9dcca59a42c708c137571d194c45bd9}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!matrix\+\_\+shortest\+\_\+path@{matrix\+\_\+shortest\+\_\+path}}
\index{matrix\+\_\+shortest\+\_\+path@{matrix\+\_\+shortest\+\_\+path}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{matrix\+\_\+shortest\+\_\+path(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::array$<$std\+::array$<$typename Graph\+Type\+::\+E\+Weight\+Type ,Graph\+Type\+::\+N\+U\+M$>$,Graph\+Type\+::\+N\+U\+M$>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::matrix\+\_\+shortest\+\_\+path (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_ab9dcca59a42c708c137571d194c45bd9}


matrix\+\_\+shortest\+\_\+path：返回所有节点对的最短路径的矩阵乘法算法。算法导论25章25.1节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定的有向图。它必须非空，否则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 一个n$\ast$n的矩阵(d\+\_\+i\+\_\+j)，其中 d\+\_\+i\+\_\+j 代表的是结点i到j的一条最短路径的权重
\end{DoxyReturn}
\subsubsection*{所有结点对的最短路径}

给定一个带权重的有向图\+G=(V,E)，其权重函数为w\+:E-\/$>$R，该函数将边映射到实值权重上。我们希望找到对于所有的结点对u,v属于\+V，找出一条从结点u 到结点v的最短路径，以及这条路径的权重。

与单源最短路径不同中使用邻接表来表示图不同，本章的多数算法使用邻接矩阵来表示图。该矩阵代表的是一个有n个结点的有向图\+G=(V,E)的边的权重\+W=(w\+\_\+i\+\_\+j)， 其中 w\+\_\+i\+\_\+j =\+:


\begin{DoxyItemize}
\item 0\+:若i=j
\item 有向边(i,j)的权重，若i!=j且(i,j)属于\+E
\item 正无穷，若 i!=j且(i,j)不属于\+E
\end{DoxyItemize}

我们允许存在负权重的边，目前仍然假定图中不存在权重为负值的环路。

本章讨论的所有结点对最短路径的算法的输出也是一个n$\ast$n的矩阵\+D=(d\+\_\+i\+\_\+j)，其中 d\+\_\+i\+\_\+j 代表的是结点i到j的一条最短路径的权重。

有时候为了解决所有结点对最短路径问题，我们不仅要计算出最短路径权重，还需要计算出前驱结点矩阵 I\+I=(pai\+\_\+i\+\_\+j)，其中 pai\+\_\+i\+\_\+j在i=j或者从i到j 不存在路径时为\+N\+I\+L，在其他情况下给出的是从结点i到结点j的某条最短路径上结点j的前驱结点。由矩阵\+I\+I的第i行所诱导的子图应当是一棵根节点为i 的最短路径树。

\subsubsection*{matrix\+\_\+shortest\+\_\+path 算法}

\paragraph*{算法原理}

matrix\+\_\+shortest\+\_\+path采用动态规划算法求解。考虑从结点i到j的一条最短路径p，假定p最多包含m条边，假定没有权重为负值的环路，且m为有限值。 如果 i=j，则p的权重为0且不包含任何边；如果i和j不同，则将路径p分解为 i--$>$k(经过路径p\textquotesingle{})--$>$j，其中路径p\textquotesingle{}最多包含m-\/1条边。

定义 l\+\_\+i\+\_\+j$<$m$>$为从结点i到j的最多包含m条边的任意路径中的最小权重，则有：l\+\_\+i\+\_\+j$<$m$>$=


\begin{DoxyItemize}
\item 0：如果i=j
\item 正无穷\+:如果 i!=j
\end{DoxyItemize}

对于m$>$=1，我们有： l\+\_\+i\+\_\+j$<$m$>$=min(l\+\_\+i\+\_\+j$<$m-\/1$>$，min\+\_\+(1$<$=k$<$=n)\{l\+\_\+i\+\_\+k$<$m-\/1$>$+w\+\_\+k\+\_\+j\})=min\+\_\+(1$<$=k$<$=n)\{l\+\_\+i\+\_\+k$<$m-\/1$>$+w\+\_\+k\+\_\+j\}。 如果图\+G不包含负值的环路，则对于每一对结点i,j，如果他们delt(i,j)$<$正无穷，则从i到j之间存在一条最短路径。由于该路径是简单路径， 则包含的边最多为n-\/1条。因此delt(i,j)=l\+\_\+i\+\_\+j$<$n-\/1$>$=l\+\_\+i\+\_\+j$<$n$>$=...

matrix\+\_\+shortest\+\_\+path算法根据输入矩阵\+W=(w\+\_\+i\+\_\+j)，计算出矩阵序列 L$<$1$>$，\+L$<$2$>$,...L$<$n-\/1$>$。最后的矩阵\+L$<$n-\/1$>$包含的是最短路径的权重。 其中\+L$<$1$>$=W。算法的核心是extend\+\_\+path函数，它将最近计算出的路径扩展了一条边

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 初始化：从图中获取权重矩阵 W
\item 执行循环扩展\+L，其中 L$<$0$>$=W, L$<$k$>$=extend\+\_\+path(L$<$k-\/1$>$,W)
\item 最终返回 L$<$N-\/1$>$
\end{DoxyItemize}

\paragraph*{算法性能}

时间复杂度\+O(\+V$^\wedge$4) 

Definition at line 129 of file matrix\+\_\+shortest\+\_\+path.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a6eb979447eeb937df4158f9646e20dde}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!matrix\+\_\+shortest\+\_\+path\+\_\+fast@{matrix\+\_\+shortest\+\_\+path\+\_\+fast}}
\index{matrix\+\_\+shortest\+\_\+path\+\_\+fast@{matrix\+\_\+shortest\+\_\+path\+\_\+fast}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{matrix\+\_\+shortest\+\_\+path\+\_\+fast(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::array$<$std\+::array$<$typename Graph\+Type\+::\+E\+Weight\+Type ,Graph\+Type\+::\+N\+U\+M$>$,Graph\+Type\+::\+N\+U\+M$>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::matrix\+\_\+shortest\+\_\+path\+\_\+fast (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a6eb979447eeb937df4158f9646e20dde}


matrix\+\_\+shortest\+\_\+path：返回所有节点对的最短路径的矩阵乘法复平方算法。算法导论25章25.1节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定的有向图。它必须非空，否则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 一个n$\ast$n的矩阵(d\+\_\+i\+\_\+j)，其中 d\+\_\+i\+\_\+j 代表的是结点i到j的一条最短路径的权重
\end{DoxyReturn}
\subsubsection*{所有结点对的最短路径}

给定一个带权重的有向图\+G=(V,E)，其权重函数为w\+:E-\/$>$R，该函数将边映射到实值权重上。我们希望找到对于所有的结点对u,v属于\+V，找出一条从结点u 到结点v的最短路径，以及这条路径的权重。

与单源最短路径不同中使用邻接表来表示图不同，本章的多数算法使用邻接矩阵来表示图。该矩阵代表的是一个有n个结点的有向图\+G=(V,E)的边的权重\+W=(w\+\_\+i\+\_\+j)， 其中 w\+\_\+i\+\_\+j =\+:


\begin{DoxyItemize}
\item 0\+:若i=j
\item 有向边(i,j)的权重，若i!=j且(i,j)属于\+E
\item 正无穷，若 i!=j且(i,j)不属于\+E
\end{DoxyItemize}

我们允许存在负权重的边，目前仍然假定图中不存在权重为负值的环路。

本章讨论的所有结点对最短路径的算法的输出也是一个n$\ast$n的矩阵\+D=(d\+\_\+i\+\_\+j)，其中 d\+\_\+i\+\_\+j 代表的是结点i到j的一条最短路径的权重。

有时候为了解决所有结点对最短路径问题，我们不仅要计算出最短路径权重，还需要计算出前驱结点矩阵 I\+I=(pai\+\_\+i\+\_\+j)，其中 pai\+\_\+i\+\_\+j在i=j或者从i到j 不存在路径时为\+N\+I\+L，在其他情况下给出的是从结点i到结点j的某条最短路径上结点j的前驱结点。由矩阵\+I\+I的第i行所诱导的子图应当是一棵根节点为i 的最短路径树。

\subsubsection*{matrix\+\_\+shortest\+\_\+path\+\_\+fast 算法}

\paragraph*{算法原理}

matrix\+\_\+shortest\+\_\+path\+\_\+fast改进了算法matrix\+\_\+shortest\+\_\+path。因为我们的目标并不是计算所有的\+L$<$m$>$矩阵，我们感兴趣的仅仅是矩阵\+L$<$n-\/1$>$。 由matrix\+\_\+shortest\+\_\+path过程定义的矩阵乘法是相关的，因此可以仅用t个矩阵乘积来计算矩阵\+L$<$n-\/1$>$，其中 n为大于lg(n-\/1)的最小整数。 因此可以用复平方技术来计算上述矩阵序列：


\begin{DoxyItemize}
\item L$<$1$>$=W
\item L$<$2$>$=W$^\wedge$2=W.\+W
\item L$<$4$>$=W$^\wedge$4=W$^\wedge$2.W$^\wedge$2
\item L$<$8$>$=W$^\wedge$8=W$^\wedge$4.W$^\wedge$4 ....
\end{DoxyItemize}

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 初始化：从图中获取权重矩阵 W
\item 执行循环扩展\+L，其中 L$<$0$>$=W, L$<$2$\ast$k$>$=extend\+\_\+path(\+L$<$k$>$,\+L$<$k$>$)
\item 最终返回 L$<$log(N-\/1)的上界整数$>$
\end{DoxyItemize}

\paragraph*{算法性能}

时间复杂度\+O(\+V$^\wedge$3lg\+V) 

Definition at line 211 of file matrix\+\_\+shortest\+\_\+path.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a97d248a07f1b31df52be3de3b5570237}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!matrix\+\_\+string@{matrix\+\_\+string}}
\index{matrix\+\_\+string@{matrix\+\_\+string}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{matrix\+\_\+string(const Matrix\+Type \&matrix)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Matrix\+Type $>$ std\+::string Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::matrix\+\_\+string (
\begin{DoxyParamCaption}
\item[{const Matrix\+Type \&}]{matrix}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a97d248a07f1b31df52be3de3b5570237}


matrix\+\_\+string：获取矩阵的字符串描述 


\begin{DoxyParams}{Parameters}
{\em matrix} & 矩阵 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 矩阵的字符串描述
\end{DoxyReturn}
获取矩阵{\ttfamily matrix}的字符串描述。 

Definition at line 169 of file header.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a27dfe859312abba6639bca7b232d4bd6}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!min\+\_\+v\+\_\+at\+\_\+\+Ef@{min\+\_\+v\+\_\+at\+\_\+\+Ef}}
\index{min\+\_\+v\+\_\+at\+\_\+\+Ef@{min\+\_\+v\+\_\+at\+\_\+\+Ef}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{min\+\_\+v\+\_\+at\+\_\+\+Ef(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type u\+\_\+id, const std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ Graph\+Type\+::\+V\+I\+D\+Type Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::min\+\_\+v\+\_\+at\+\_\+\+Ef (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{u\+\_\+id, }
\item[{const std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&}]{flow}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a27dfe859312abba6639bca7b232d4bd6}


min\+\_\+v\+\_\+at\+\_\+\+Ef：relabel操作中的min\+\_\+v\+\_\+at\+\_\+\+Ef操作。算法导论26章26.4节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em u\+\_\+id} & 结点u的id，必须有效否则抛出异常 \\
\hline
{\em flow} & 预流 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 所有边(u,v)属于\+E\+\_\+f(残留网络\+G\+\_\+f中的边)中，高度最小的结点v
\end{DoxyReturn}
该方法扫描\+Ef中所有从u出发的边(u,v)，找出高度最小的结点v 

Definition at line 124 of file genericpushrelabel.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_aba1581358d79ba82dc4fd0c15bc987e6}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!prim@{prim}}
\index{prim@{prim}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{prim(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type source\+\_\+id, Action\+Type pre\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type)\lcurly{}\rcurly{}, Action\+Type post\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type)\lcurly{}\rcurly{})}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type , typename Action\+Type  = std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type)$>$$>$ Graph\+Type\+::\+E\+Weight\+Type Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::prim (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{source\+\_\+id, }
\item[{Action\+Type}]{pre\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType)\{\}}, }
\item[{Action\+Type}]{post\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType)\{\}}}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_aba1581358d79ba82dc4fd0c15bc987e6}


prim：最小生成树的\+Prim算法，算法导论23章23.2节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强指针，必须非空。若为空则抛出异常} & \\
\hline
{\em source\+\_\+id：最小生成树的根结点$<$tt$>$id$<$/tt$>$，必须有效。若无效则抛出异常} & \\
\hline
{\em pre\+\_\+action\+:一个可调用对象，在每次从最小优先级队列中弹出最小顶点时立即调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
{\em post\+\_\+action\+:一个可调用对象，在每次从最小优先级队列中弹出最小顶点并处理完它的边时立即调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 最小生成树的权重
\end{DoxyReturn}
{\ttfamily source\+\_\+id}在以下情况下无效：


\begin{DoxyItemize}
\item {\ttfamily source\+\_\+id}不在区间{\ttfamily \mbox{[}0,N)}之间时，{\ttfamily source\+\_\+id}无效
\item {\ttfamily graph}中不存在某个顶点的{\ttfamily id}等于{\ttfamily source\+\_\+id}时，{\ttfamily source\+\_\+id}无效
\end{DoxyItemize}

\subsubsection*{最小生成树}

最小生成树：对于一个连通无向图\+G=(V,E)，对于每一条边(u,v)属于\+E都赋予了一个权重w(u,v)。我们希望找出一个无环子集\+T，其中\+T为\+E的子集，使得所有的顶点\+V位于\+T中， 同时\+T具有最小的权重。由于\+T是无环的，且连通所有结点因此\+T必然是一棵树。我们称这样的树为生成树。称从\+G中求取该生成树的问题为最小生成树问题。

通用的最小生成树使用贪心策略。该策略在每个时刻找到最小生成树的一条边，并在整个策略过程中维持循环不变式：边的集合\+A在每次循环之前是某棵最小生成树的一个子集。

在每一步，选择一条边(u,v)，将其加入集合\+A中，使得\+A不违反循环不变式。称这样的边(u,v)为边集合\+A的安全边。

\subsubsection*{Prim算法}

\paragraph*{算法原理}

在\+Prim算法所具有的一个性质是集合\+A中的边总是构成一棵树。这棵树从一个任意的根结点r开始，一直长大到覆盖\+V中的所有结点为止。算法每一步在连接集合\+A和\+A之外的结点的所有边中， 选择一条边加入到\+A中（经特殊选择的边）。

为了有效地实现\+Prim算法，需要一种快速的方法来选择一条新的边以便加入到由集合\+A中的边所构成的树中。在算法执行过程中，所有不在树\+A中的结点都存放在一个基于key的属性的最小优先级队列\+Q中。 对于每个结点v，属性v.\+key保存的是连接v和树中结点的所有边中最小边的权重。若这样的边不存在则权重为正无穷。属性v.\+pai给出的是结点v在树中的父结点。

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 初始化：将所有结点的key设为正无穷，所有结点的父结点置为空(结点构造时，父结点默认为空）
\item 设置源点：将源点的key设为0，
\item 构造最小优先级队列：将所有顶点放入最小优先级队列\+Q中
\item 循环，直到最小优先级队列为空。循环中执行下列操作：
\begin{DoxyItemize}
\item 弹出最小优先级队列的头部顶点u
\item 从结点u出发的所有边，找出它的另一端的结点v。如果v也在\+Q中，且w(u,v)$<$v.\+key，则证明(u,v)是v到集合\+A的最短边，因此设置v.\+pai=u,v.\+key=w(u,v) $>$这里隐含着一个最小优先级队列的decreate\+\_\+key操作
\end{DoxyItemize}
\end{DoxyItemize}

\paragraph*{算法性能}

Prim总时间代价为\+O(Vlg\+V+\+Elg\+V)=O(\+Elg\+V)(使用最小堆实现的最小优先级队列），或者\+O(E+\+Vlg\+V)（使用斐波那契堆实现最小优先级队列） 

Definition at line 77 of file prim.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_abd520b7e33d8c1e72b05210d784ac258}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!push@{push}}
\index{push@{push}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{push(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type u\+\_\+id, typename Graph\+Type\+::\+V\+I\+D\+Type v\+\_\+id, std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::push (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{u\+\_\+id, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{v\+\_\+id, }
\item[{std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&}]{flow}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_abd520b7e33d8c1e72b05210d784ac258}


push：generic\+\_\+push\+\_\+relabel算法的push操作。算法导论26章26.4节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em u\+\_\+id} & 结点u的id，必须有效否则抛出异常 \\
\hline
{\em v\+\_\+id} & 结点v的id，必须有效否则抛出异常 \\
\hline
{\em flow} & 预流的引用（执行过程中会更新预流） \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: void
\end{DoxyReturn}
如果u\+\_\+id或者v\+\_\+id无效，则抛出异常：


\begin{DoxyItemize}
\item 如果指定的顶点{\ttfamily id}不在{\ttfamily \mbox{[}0,N)}之间，则无效
\item 如果不存在某个顶点与指定的顶点{\ttfamily id}相同，则无效
\end{DoxyItemize}

如果一个结点 u是一个溢出结点，则至少有一条入边，假设为(v,u)，且f(v,u)$>$0。此时残留网络\+G\+\_\+f中的边c\+\_\+f(u,v)$>$0。如果此时还有h(u)=h(v)+1， 则可以对边(u,v)执行push操作。

因为结点u有一个正的超额流u.\+e，且边(u,v)的残余容量为正，因此可以增加结点u到v的流，增加的幅度为min(u.\+e,c\+\_\+f(u,v))，这种幅度的增加不会导致 u.\+e为负值或者容量 c(u,v) 被突破

push操作步骤：


\begin{DoxyItemize}
\item 计算残余容量 c\+\_\+f(u,v)
\item 计算流的增加幅度 delt\+\_\+f=min(u.\+e,c\+\_\+f(u,v))
\item 更新流：
\begin{DoxyItemize}
\item 如果 (u,v) 属于 E，则 f(u,v) += delt\+\_\+f
\item 如果 (v,u) 属于 E，则 f(v,u) -\/= delt\+\_\+f
\end{DoxyItemize}
\item 更新溢出流量：
\begin{DoxyItemize}
\item u.\+e -\/= delt(u,v)
\item v.\+e += delt(u,v)
\end{DoxyItemize}
\end{DoxyItemize}

\begin{quote}

\begin{DoxyItemize}
\item 由顶点的{\ttfamily key}属性存储超额流量e $\ast$
\item 执行push(u,v)时，要求存在残留边 (u,v)属于\+Ef，且c\+\_\+f(u,v)$>$0；否则抛出异常
\item 执行push(u,v)时，要求 u.\+e$>$0；否则抛出异常
\end{DoxyItemize}\end{quote}


Definition at line 67 of file genericpushrelabel.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a143924362cc9f23ca452c3ca0e292ff3}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!relabel@{relabel}}
\index{relabel@{relabel}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{relabel(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type u\+\_\+id, const std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&flow)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::relabel (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{u\+\_\+id, }
\item[{const std\+::array$<$ std\+::array$<$ typename Graph\+Type\+::\+E\+Weight\+Type, Graph\+Type\+::\+N\+U\+M $>$, Graph\+Type\+::\+N\+U\+M $>$ \&}]{flow}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a143924362cc9f23ca452c3ca0e292ff3}


relabel：generic\+\_\+push\+\_\+relabel算法的relabel操作。算法导论26章26.4节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em u\+\_\+id} & 结点u的id，必须有效否则抛出异常 \\
\hline
{\em flow} & 预流 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: void
\end{DoxyReturn}
如果结点u溢出（如果不是溢出则抛出异常），并且对于所有边(u,v)属于\+E\+\_\+f(残留网络\+G\+\_\+f中的边)，有u.\+h$<$=v.\+h，则可以对结点u执行relabel操作。 当调用relabel操作时，\+E\+\_\+f必须包含至少一条从结点u出发的边，否则抛出异常。

relabel 步骤：


\begin{DoxyItemize}
\item 计算 min\{v.\+h\+:(u,v)属于\+E\+\_\+f\}
\item u.\+h=1+ min\{v.\+h\+:(u,v)属于\+E\+\_\+f\}
\end{DoxyItemize}

当对于存在边(u,v)属于\+E\+\_\+f(残留网络\+G\+\_\+f中的边)，有u.\+h$>$v.\+h时，抛出异常 

Definition at line 184 of file genericpushrelabel.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_abafb73bda29c4e389edb048a5e5d8d2b}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!relabel\+\_\+to\+\_\+front@{relabel\+\_\+to\+\_\+front}}
\index{relabel\+\_\+to\+\_\+front@{relabel\+\_\+to\+\_\+front}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{relabel\+\_\+to\+\_\+front(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type src, typename Graph\+Type\+::\+V\+I\+D\+Type dst)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::array$<$std\+::array$<$typename Graph\+Type\+::\+E\+Weight\+Type,Graph\+Type\+::\+N\+U\+M$>$,Graph\+Type\+::\+N\+U\+M$>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::relabel\+\_\+to\+\_\+front (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{src, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{dst}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_abafb73bda29c4e389edb048a5e5d8d2b}


relabel\+\_\+to\+\_\+front：最大流的前置重贴标签算法。算法导论26章26.5节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指定流网络。它必须非空，否则抛出异常} & \\
\hline
{\em src} & 流的源点，必须有效否则抛出异常 \\
\hline
{\em dst} & 流的汇点，必须有效否则抛出异常 \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: 最大流矩阵
\end{DoxyReturn}
如果src、dst任何一个顶点无效，则抛出异常：


\begin{DoxyItemize}
\item 如果指定的顶点{\ttfamily id}不在{\ttfamily \mbox{[}0,N)}之间，则无效
\item 如果不存在某个顶点与指定的顶点{\ttfamily id}相同，则无效
\end{DoxyItemize}

\subsubsection*{最大流}

流网络\+G=（\+V,E）是一个有向图，图中每条边(u,v)属于\+E都有一个正的容量值c(u,v)$>$0。而且如果边集合\+E中包含一条边(u,v)，则图中不存在反向边 (v,u)。为方便起见，假设(u,v)不属于\+E,定义c(u,v)=0（即无效权重为0），并且在图中不允许自循环。

在流网络中存在两个特殊点：源结点s和汇点t。假定每一个结点都在从源点s到汇点t的某条路径上。即对于每个结点v属于\+E，存在某条路径 s--$>$v--$>$t。

G中的流是一个实值函数f\+:V$\ast$\+V--$>$R，满足下面两条性质：


\begin{DoxyItemize}
\item 容量限制：对于所有结点u,v属于\+V，要求0$<$= f(u,v) $<$= c(u,v)
\item 流量守恒： 对于所有结点u属于\+V-\/\{s,t\}，要求：从u进入的流等于从u出去的流
\end{DoxyItemize}

对于(u,v)不属于\+E的情况，从结点u到v之间没有流，因此f(u,v)=0。我们称非负数值f(u,v)为从结点u到v的流。一个流f的值 $\vert$f$\vert$=从源点流出的总流量-\/ 流入源结点的总流量

最大流问题：给定流网络\+G、一个源结点s、一个汇点t,找出值最大的一个流

\subsubsection*{relabel\+\_\+to\+\_\+front 算法}

\paragraph*{算法原理}

$>$本节的一些概念参考 generic\+\_\+push\+\_\+relabel 算法

推送-\/重贴标签方法允许我们以任意次序执行基本操作。但是，如果仔细选择这个次序，并且对网络数据结构进行高效管理，我们可以获取更高的算法性能。

前置重贴标签算法在执行过程中维持一个网络中的结点的链表。算法从头到尾对链表进行扫描，每次选择一个溢出结点u。 然后对结点u进行“释放”，即对所选结点执行推送操作和重贴标签操作，直到结点u不再拥有正值的超额流量为止。 每次在算法对一个结点进行重贴标签操作时，我们都将该结点移动到链表的最前面（也就是“前置重贴标签算法”的名字由来），然后算法进行一次新的扫描。

设图\+G=(V,E)是一个源点s汇点t的流网络，f是\+G中的一个预流（它满足容量限制单不满足流量守恒性质），h是一个高度函数。 对于边(u,v)，如果c\+\_\+f(u,v)$>$0且h(u)=h(v)+1，则边(u,v)是一条许可边；否则边(u,v)是一条非许可边。许可边意义是：在残余网络中， 流可以经过它进行推送的边。许可网络指图\+G\+\_\+f\+\_\+h=(V,E\+\_\+f\+\_\+h)，其中\+E\+\_\+f\+\_\+h是许可边的集合。

在前置重贴标签算法中，我们将所有边都组织为“邻接链表”。给定流网络\+G=(V,E)，对于结点u属于\+V，其邻接链表u.\+N是结点u在图\+G 中的邻接结点所构成的一个单链表（包括了u的上游和下游的邻接结点）：若边(u,v)属于\+E或者边(v,u)属于\+E，则结点v将出现在链表u.\+N中。 $>$邻接链表u.\+N包含的结点是所有可能存在残留边(u,v)的结点v

属性u.\+N.\+head指向的是邻接表u.\+N中的第一个结点；v.\+next-\/neighbor指向的是邻接链表u.N中位于结点v后面的一个结点。如果v是链表中最后一个结点， 则该指针的值为\+N\+I\+L

前置重贴标签算法以任意次序遍历每一个邻接链表，该次序在算法整个执行过程中不变。对于每个结点u，属性u.\+current指向的是u.\+N 链表中当前正在考虑的结点。初始情况下u.\+current指向u.\+N.\+head

\paragraph*{基本操作}

\subparagraph*{discharge 操作}

对于溢出结点u,如果将其所有多余的流通过许可边推送到相邻的结点上，则称该结点得到释放。 在释放过程中，需要对结点u进行重贴标签操作，这使得从结点u发出的边成为许可边。discharge(u) 操作步骤如下：


\begin{DoxyItemize}
\item 循环，条件为u.\+e$>$0，循环内操作为：
\begin{DoxyItemize}
\item 获取u.\+current，假设为v
\item 如果v为空，即遍历到u.\+N链表的末尾，则对u执行relabel操作，然后将u.\+current指向u.\+N链表的头部
\item 如果 v非空，且满足 push 操作的条件(c\+\_\+f(u,v)$>$0且 u.\+h=v.\+h+1)，则执行push操作
\item 如果 v 非空，但不满足 push 操作，则 u.\+current指向u.\+N链表的下一个结点
\end{DoxyItemize}
\end{DoxyItemize}

\paragraph*{算法步骤}


\begin{DoxyItemize}
\item 初始化预流操作（与 generic\+\_\+push\+\_\+relabel 算法相同）
\item 对所有的非s、t的结点，将它们加入到链表\+L中（顺序任意）
\item 对所有的非s、t的结点u,初始化u.\+current为u.\+N.\+head
\item 设置u为\+L.\+head
\item 循环，条件为u!=N\+I\+L，循环中操作：
\begin{DoxyItemize}
\item 保留u.\+h为oldh
\item 对u执行discharge操作
\item 如果u.\+h$>$oldh，证明对u执行了重贴标签操作，此时将u移动到\+L的头部
\item u=u.\+next（提取u在\+L中的下一个）
\end{DoxyItemize}
\end{DoxyItemize}

\paragraph*{算法性能}

算法性能：时间复杂度 O(\+V$^\wedge$3) 

Definition at line 280 of file relabeltofront.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_afe2bd83fca7df7e07ece9a59b8e7f5a6}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!relax@{relax}}
\index{relax@{relax}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{relax(std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$ from, std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$ to, typename Vertex\+Type\+::\+Key\+Type weight)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Vertex\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::relax (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$}]{from, }
\item[{std\+::shared\+\_\+ptr$<$ Vertex\+Type $>$}]{to, }
\item[{typename Vertex\+Type\+::\+Key\+Type}]{weight}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_afe2bd83fca7df7e07ece9a59b8e7f5a6}


relax：单源最短路径的松弛操作，算法导论24章24.1节 


\begin{DoxyParams}{Parameters}
{\em from\+:松弛有向边的起始结点，必须非空。若为空则抛出异常} & \\
\hline
{\em to：松弛有向边的终止结点，必须非空且不等于from。若为空或者等于from则抛出异常} & \\
\hline
{\em weight\+:有向边的权重} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+: void
\end{DoxyReturn}
对每一个结点v来说，我们维持一个属性v.\+key，它记录了从源结点s到结点v的最短路径权重的上界。我们称v.\+key为s到v的最短路径估计。

松弛过程是测试一下是否可以对从s到v的最短路径进行改善的过程，测试方法为： 将结点s到u之间的最短路径估计加上(u,v)边的权重，并与当前的s到v之间的最短路径估计进行比较。如果前者较小则对v.\+key和v.\+parent进行更新。

性能：时间复杂度\+O(1) 

Definition at line 82 of file bellmanford.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_ac368f242de9f06c7d936cba4aa0ab40b}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!same\+\_\+component@{same\+\_\+component}}
\index{same\+\_\+component@{same\+\_\+component}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{same\+\_\+component(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type id1, typename Graph\+Type\+::\+V\+I\+D\+Type id2)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ bool Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::same\+\_\+component (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{id1, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{id2}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_ac368f242de9f06c7d936cba4aa0ab40b}


same\+\_\+component：返回无向图的两个顶点是否位于同一个连通分量中。算法导论21章21.1节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强指针，必须非空。若为空则抛出异常} & \\
\hline
{\em id1\+:第一个顶点，必须有效。若无效则抛出异常} & \\
\hline
{\em id2\+:第二个顶点，必须有效。若无效则抛出异常} & 当满足以下条件之一时，id无效的情况：\\
\hline
\end{DoxyParams}

\begin{DoxyItemize}
\item id小于0或者大于等于{\ttfamily Graph\+Type\+::\+N\+U\+M}
\item {\ttfamily graph-\/$>$vertexes.\+at(id1)}为空
\end{DoxyItemize}

在执行 same\+\_\+component函数之前必须先执行 connected\+\_\+component函数对无向图进行预处理。 

Definition at line 93 of file connectedcomponent.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a6d058c2aaa8714778b3f2ab8a24ff232}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!scc@{scc}}
\index{scc@{scc}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{scc(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ const std\+::vector$<$std\+::vector$<$typename Graph\+Type\+::\+V\+I\+D\+Type$>$ $>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::scc (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a6d058c2aaa8714778b3f2ab8a24ff232}


scc：强连通分量，算法导论22章22.5节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强引用，必须非空。若为空则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+:强连通分量的{\ttfamily std\+::vector}，每一个强连通分量，由一组顶点{\ttfamily id}组成的{\ttfamily std\+::vector}表示。
\end{DoxyReturn}
有向图\+G=(V,E)的强连通分量是一个最大结点集合\+C，\+C是\+V的子集。对于\+C中的任意一对结点u,v来说，路径u--$>$v和路径v--$>$u同时存在。即结点u和结点v之间相互可以到达。

在强连通分量的算法中，需要用到图\+G的转置\+G\+\_\+\+T。定义\+G\+\_\+\+T=(V,E\+\_\+\+T),其中\+E\+\_\+\+T=\{(u,v)\+:(v,u)属于\+E\}，即\+G\+\_\+\+T中的边是\+G中的边进行反向获得。


\begin{DoxyItemize}
\item 图\+G和图\+G\+\_\+\+T的强连通分量相同
\item 可以证明，{\ttfamily scc}算法得到的就是强连通分量。证明见《算法导论》
\end{DoxyItemize}

强连通分量算法步骤：


\begin{DoxyItemize}
\item 对原图\+G执行深度优先搜索，并获取每个结点的完成时间 finish\+\_\+time
\item 对转置图\+G\+\_\+\+T执行深度优先搜索，但是按照 G中结点的一个排序来搜索（这个排序是按照finish\+\_\+time的降序）
\item G\+\_\+\+T的深度优先森林就是强连通分量
\end{DoxyItemize}

性能：时间复杂度\+O(V+\+E) 

Definition at line 48 of file strongconnectedcomponent.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a804241e72be5f4c031190bc12a6b73a2}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!topology\+\_\+sort@{topology\+\_\+sort}}
\index{topology\+\_\+sort@{topology\+\_\+sort}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{topology\+\_\+sort(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph)}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ std\+::vector$<$typename Graph\+Type\+::\+V\+I\+D\+Type$>$ Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::topology\+\_\+sort (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a804241e72be5f4c031190bc12a6b73a2}


topology\+\_\+sort：拓扑排序，算法导论22章22.4节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强引用，必须非空。若为空则抛出异常} & \\
\hline
\end{DoxyParams}
\begin{DoxyReturn}{Returns}
\+:拓扑排序结果，它是顶点{\ttfamily id}组成的{\ttfamily std\+::vector}，表示顶点的拓扑排序后的顺序
\end{DoxyReturn}
对于一个有向无环图\+G=（\+V，\+E)，其拓扑排序是\+G中所有结点的一种线性次序，该次序满足如下条件： 如果图\+G包含边(u,v)，则结点u在拓扑排序中处于结点v的前面。

拓扑排序原理：对有向无环图\+G进行深度优先搜索。每当完成一个结点时，将该结点插入到拓扑排序结果的头部。 因此如果将结点按照完成时间降序排列，则得到的就是拓扑排序的结果。

引理：一个有向图\+G=(V,E)是无环的当且仅当对其进行深度优先搜索时不产生后向边。

性能：时间复杂度\+O(V+\+E) 

Definition at line 45 of file topologysort.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a19237111c3b1ec2717c5e1aefe2f6d9b}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!unlimit@{unlimit}}
\index{unlimit@{unlimit}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{unlimit()}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename T $>$ T Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::unlimit (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a19237111c3b1ec2717c5e1aefe2f6d9b}


unlimit：返回正无穷的函数 

\begin{DoxyReturn}{Returns}
\+: 正无穷大的数
\end{DoxyReturn}
将本函数的返回值定义为正无穷。在算法导论图算法中，经常用到正无穷。通常对正无穷的操作是\+:


\begin{DoxyItemize}
\item 将边的权重或者节点的{\ttfamily key}设为正无穷
\item 对正无穷加、减一个有限的数，结果还是正无穷
\end{DoxyItemize}

这里将{\ttfamily std\+::numeric\+\_\+limits$<$T$>$\+::max()/2}设为正无穷，考虑到正无穷加上一个较大的数必须保证不能溢出 

Definition at line 111 of file header.\+h.

\hypertarget{namespace_introduction_to_algorithm_1_1_graph_algorithm_a5fbba98b1c6a8b55f026158acc815768}{}\index{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}!visit@{visit}}
\index{visit@{visit}!Introduction\+To\+Algorithm\+::\+Graph\+Algorithm@{Introduction\+To\+Algorithm\+::\+Graph\+Algorithm}}
\subsubsection[{visit(std\+::shared\+\_\+ptr$<$ Graph\+Type $>$ graph, typename Graph\+Type\+::\+V\+I\+D\+Type v\+\_\+id, int \&time, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ pre\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type, int)\lcurly{}\rcurly{}, std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$ post\+\_\+action=[](typename Graph\+Type\+::\+V\+I\+D\+Type, int)\lcurly{}\rcurly{})}]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Graph\+Type $>$ void Introduction\+To\+Algorithm\+::\+Graph\+Algorithm\+::visit (
\begin{DoxyParamCaption}
\item[{std\+::shared\+\_\+ptr$<$ Graph\+Type $>$}]{graph, }
\item[{typename Graph\+Type\+::\+V\+I\+D\+Type}]{v\+\_\+id, }
\item[{int \&}]{time, }
\item[{std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$}]{pre\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType,int)\{\}}, }
\item[{std\+::function$<$ void(typename Graph\+Type\+::\+V\+I\+D\+Type, int)$>$}]{post\+\_\+action = {\ttfamily \mbox{[}\mbox{]}(typename~GraphType\+:\+:VIDType,int)\{\}}}
\end{DoxyParamCaption}
)}\label{namespace_introduction_to_algorithm_1_1_graph_algorithm_a5fbba98b1c6a8b55f026158acc815768}


visit：深度优先搜索的辅助函数，用于访问顶点，算法导论22章22.3节 


\begin{DoxyParams}{Parameters}
{\em graph\+:指向图的强引用，必须非空。若为空则抛出异常} & \\
\hline
{\em v\+\_\+id\+:待访问顶点的$<$tt$>$id$<$/tt$>$，必须有效。如果无效则抛出异常} & \\
\hline
{\em time\+:访问时刻，是一个引用参数，确保每次$<$tt$>$visit$<$/tt$>$都访问同一个时钟。} & \\
\hline
{\em pre\+\_\+action\+:一个可调用对象，在每次发现一个顶点时调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$以及发现时间$<$tt$>$time$<$/tt$>$。默认为空操作，即不进行任何操作} & \\
\hline
{\em post\+\_\+action\+:一个可调用对象，在每次对一个顶点搜索完成时调用，调用参数为该顶点的$<$tt$>$id$<$/tt$>$以及完成时间$<$tt$>$time$<$/tt$>$。默认为空操作，即不进行任何操作} & {\ttfamily v\+\_\+id}在以下情况下无效：\\
\hline
\end{DoxyParams}

\begin{DoxyItemize}
\item {\ttfamily v\+\_\+id}不在区间{\ttfamily \mbox{[}0,N)}之间时，{\ttfamily v\+\_\+id}无效
\item {\ttfamily graph}中不存在某个顶点的{\ttfamily id}等于{\ttfamily v\+\_\+id}时，{\ttfamily v\+\_\+id}无效
\end{DoxyItemize}

在每次对一个结点调用visit的过程中，结点v\+\_\+id的初始颜色都是白色。然后执行下列步骤：


\begin{DoxyItemize}
\item 将全局时间 time 递增
\item 发现结点 v\+\_\+id
\item 对结点 v\+\_\+id 的每一个相邻结点进行检查，在相邻结点是白色的情况下递归访问该相邻结点
\item 当结点 v\+\_\+id 的相邻结点访问完毕，则全局时间 time 递增，然后将结点 v\+\_\+id 设置为完成状态 
\end{DoxyItemize}

Definition at line 49 of file dfs.\+h.

